Boost logo

Boost :

Subject: Re: [boost] New library in the Vault: ConstantTimeSize
From: David Abrahams (dave_at_[hidden])
Date: 2008-10-16 17:44:05

on Thu Oct 16 2008, "Simonson, Lucanus J" <> wrote:

> Do we know that loop unrolling of iteration over a linked list is
> profitable?

Nope, not for sure.

> I would think that a conscientious programmer interested in
> loop unrolling of linked lists should pursue an analysis to measure the
> potential benefits that might be realized with current compilers and
> hardware before implementing a general solution along those lines. This
> analysis would be somewhat challenging, because it is likely that a toy
> testcase would fit in L1 cache and show promising results while
> realistic usage of lists would lead to their elements being fragmented
> in the heap and a large proportion of L1 and L2 cache misses that
> dominates runtime for loop iteration. If the long latency cache miss
> dominates the overhead of checking if itr == list.end() you will realize
> no benefit from loop unrolling on a modern architecture which can mask
> the latency of the comparison and overhead of the branch instruction
> that depends upon it within the latency of the cache miss of the next
> iteration of the loop under speculative execution. It is conceivable
> that the benefit would be negligible in the common case. We won't know,
> however, unless someone does the analysis.

Good points. I first realized the importance of O(1) size in the
context of TMP, and translated my conclusions to the runtime world
without considering cache effects. Testing is definitely needed.

Dave Abrahams
BoostPro Computing

Boost list run by bdawes at, gregod at, cpdaniel at, john at