Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: David Bergman (David.Bergman_at_[hidden])
Date: 2009-06-10 14:23:42

On Jun 10, 2009, at 2:16 PM, Simonson, Lucanus J wrote:

> David Bergman wrote:
>>>>>
>>>>> Ok, so you could use Thorsten's auto_buffer as your storage, which
>>>>> actually would give you, potentially, the best of two worlds
>>>>> (allocation speed and - you seem to push this angle - cache) and
>>>>> dynamic heap beyond that initial segment.
>>>>
>>>>
>>>> Cache coherency is King!
>>
>> Yes, I have noticed that you push that angle very hard.
>>
> ...
>> 2. Why is cache coherency so much better when you use an inline array
>> then when Thorsten does it? He also allocates inline (at first) and
>> you only have a first, anyway. So, can you please explain why cache
>> coherency is so much more King in your...
>
> Cache coherency is I think a misapplied term here.

I know, that is why I put apostrophes around it when initially talking  
about it; but that seemed to be the preferred term, with it being King  
and all.

Yes, I am talking about locality of reference, and used basically the  
arguments you do here in order to get the idea that stacks are somehow  
intrinsically more cache-friendly than the heap out of somebody's  
head...

/David

>  What you two seem to be talking about is spatial locality of  
> reference.  The stack typically has good spatial locality of  
> reference relative to the heap because it is contiguous.  A vector  
> or similar contiguous data structure always has good spatial  
> locality of reference because it is contiguous unless it is very  
> small.  You will have no significant benefit from allocating a  
> vector on the stack vs. the heap if it is very large because 1) your  
> dynamic allocation cost is ammoratized over a very large number of  
> vector elements and 2) the benefit from the first few elements  
> already being in cache because of being on the stack is amoratized  
> over a very large number of elements that are likely not in the  
> cache and will perform the same as if allocated on the heap.   
> Furthermore, the performance benefit of allocating a small vector on  
> the stack as opposed to the heap will be dominated by the time saved  
> by not going to to the dynamic
>  memory allocation routine as opposed to the cache misses caused by  
> the dynamic memory allocated being cold.  Both of these performance  
> concerns can be improved by pooling allocators.  I question the  
> benfit of this stack vs. heap based allocation for containers when  
> the termonology used to describe its benefit is misapplied.  By the  
> way, allocating large containers on the stack is an extremely,  
> extremely foolish thing to do because it causes crashes and  
> performance problems.
>
> Cache coherency is a concurrency issue where multiple processors (or  
> cores) are sharing memory and when modifying the shared memory in  
> their cache need to make sure that the cached version of the same  
> address is also modified in the caches of other cores/processors.   
> It is a serious problem when you have to handle it in software, and  
> is best solved by hardware, which is tricky and expensive.  Cell  
> processors do not have hardware cache coherency, while intel  
> processors do.  Since you don't have to worry about cache coherency  
> in general, and when you do need to worry about it your life is hell  
> and you definitely know it, and since it is only an issue on some  
> platforms, I doubt any boost library should ever consider the issue  
> of cache coherency at all.
>
> Regards,
> Luke
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost