Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-06-12 11:51:30

Christian Schladetsch wrote:
> Note that your test case is ~8% faster when implemented using
> monotonic::vector over using std::vector. This is because the monotonic
> vector is using the stack for storage, where the loop controls and other
> fields are also.

How do you know?  Unless you went in and measured with vtune how many cache misses you get with each you are just making things up and stating them as fact.  I highly doubt the difference is due to improved spatial locality from allocation being on the stack.

Frank Mori Hess wrote:
> Are you setting _SCL_SECURE to zero on msvc?  It's a common cause of
> performance drops with std containers on msvc.
> 
How many times has someone come to boost with an optimization that isn't because they don't know about _SCL_SECURE?  This is how the stl gets the reputation of being slow which so damages people's ability to write sensible code.  Forcing everyone who is ignorant of what the compiler is doing to write containers with bugs in them because they don't like the fact that stl is made slow by default in MSVC is hardly improving security.

Storing all the nodes of a tree in a buffer instead of scattered in the heap is a good idea.  Storing all the nodes of a tree in a buffer of a fixed size that causes a crash when you exceed it is a bad idea.  We get massive performance improvements by using a (non-standard) memory buffer allocator in internal code that implements a variant of R*Tree.  We don't crash if we keep adding elements to the tree.  We find that in toy benchmarks like Christian shows the performance advantage of storing the nodes of a tree in a contiguous buffer is greatly less than in a real application because even the system allocator will cluster them together in memory when memory is completely free and because everything in a toy benchmark fits in cache anyway.  What Christian is trying to do is in general good, but this idea that allocating the buffer on the stack is somehow a great idea seems to be getting in the way of the portion of his overall proposal that is actually good.  He also hasn't yet addressed the design flaw which makes his data structures unsafe to use.  Performance at the expense of safety is easy to achieve, just program in C.

Instead of reinventing the wheel perhaps can we just find some good allocators people have written and compare them?  Since there is no std::R*Tree and no way Christian would implement monotonic::R*Tree it would be better to provide a standard compliant allocator people can use on their own containers that are modeled after the standard than re-implement the stl containers with a non-standard compliant allocator.

Luke