Re: Array vs. Linked List Traversal

jseigh <jseigh_es00@xemaps.com> writes:

Array elements being in cache, assuming the element size is small
enough to fit multiple elements in a cache line?

Yes.  Even without, hardware branch predictors will see the stride and
prefetch the cache lines appropriately.

No dependent load delay from having to load the linked list next
pointer?  If that was the case, then moving the load of the next
pointer to the beginning of the loop should ameliorate that somewhat.

Depends on how much work you have to do per element.  If it's just a
little work, like adding up one field of each element, or searching
for a particular value of a field, the linked-list will mean that each
iteration takes 4-5 cycles on a modern CPU even on a D-cache hit,
while such loops may take 1 cycle/iteration or less if an array is
used.  If you have more than 5 cycles of work per element, then that's
not an issue (as long as the elements are in the D-cache or the
linked-list layout works for the hardware prefetchers), but modern
CPUs can do a lot in 5 cycles.

Rearranging the load of the next pointer will typically not make a big
difference on OoO CPUs, unless you have a lot of branch
mispredictions.

Something else?

Please limit your lines to around 70 characters.  I reformatted the
quoted material.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
  Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>