Which do you expect will be faster,
./listinsert -u or
and why? Come to a consensus about your answer.
We did not reach this activity in lecture.
Which of the following are the most likely explanation(s) for the difference
in performance between
./listinsert -r 100000 and
./listinsert -u 100000?
(If 100000 takes too long, try 20000. The difference gets more dramatic as you
raise the number of elements.)
./listinsert -r inserts elements in random order, so the average
-r must examine more list nodes than the average insertion
./listinsert -u under this memory allocator exhibits a more
predictable pattern of memory accesses, allowing the processor to better
optimize its access of memory.
./listinsert -u inserts elements in predictable order, allowing the
processor to predict which element will be inserted next and optimize the