Talk:SE250:HTTB:WIP:Array-based Lists:Screencasts:sdal039

Nice concise screencast. Your diagrams explain things correctly, but your code is wrong and the observation about the runtime is irrelevant. Realloc is not unreliable. You are malloc'ing an unreasonably large block of memory, then calling realloc on a very small amount (try printing out sizeof(arr) — I think you'll find it is 4 bytes only).

The code we want to compare is:

     element_t* newarr = malloc( required_capacity * sizeof( element_t ) );
     memmove( newarr, alist->arr, alist->length * sizeof(element_t) );
     free( alist->arr );

compared with

     alist->arr = realloc( alist->arr, required_capacity * sizeof(element_t) );

The former always allocates a new memory block, whereas the latter only does so if there is another allocation preventing expansion of the current memory block. In a "real" program, expansion is almost always blocked. In our benchmark experiment, it never is.

Jham005 16:30, 22 April 2008 (NZST)