Subject: Re: [geometry] 1.57 Storing indices as values to save space.
From: Tim Finer (tim.finer_at_[hidden])
Date: 2014-11-26 18:56:51
Hi Adam,
On 11/26/14, 11:49 AM, Adam Wulkiewicz wrote:
> Hi Tim,
>
> Tim Finer wrote:
>> Hi Adam,
>>
>> Actually, I think what rtree is doing with the temporary vector in
>> the packing constructor should be considered a bug.
>>
>> That problem is that the vector is created without regard to the
>> rtree's allocator - so even if a user gives the rtree a memory mapped
>> file allocator, the rtree creates a copy of the incoming data in
>> memory, ignoring the allocator.
>>
>
> Not really a copy of incoming data. A calculated centroids and
> iterators to the original data.
Ah I see. IndexableGetter must be the source for the centroid though,
right? Can you use the IndexableGetter to calculate and sort on the
centroid without allocating a temporary vector of them?
>
> Yes, rtree's allocator could be passed to the vector (as mentioned in
> the other email). Then iterators shouldn't be stored since they might
> be not suitable for storing in shared memory. So probably a copy of
> actual objects should be made here. And this could be done only if an
> allocator was different than std::allocator<> so at least in this case
> it wouldn't harm the performance. Also in the case of passing
> RandomAccessIterators elements indexes could be stored instead of
> iterators.
Except I think the word "should" belongs there instead of "could". :)
The whole point of passing in an allocator is for naught if the class
selectively uses it - it doesn't matter about shared memory allocators
or not. All of the classes that I'm familiar with that use an allocator
use it completely (like the stdlib containers).
Step back from your knowledge of the implementation and think about this
as a user of the rtree. Would you really expect the rtree to allocate
space from the heap, after giving it an allocator?
The rtree shouldn't second guess the intentions of the users here and
allocate memory from the heap for a temporary structure. There are
plenty of important uses cases to use other kinds of allocators that
don't have anything to do with shared or mapped memory: debugging
allocators, small object allocators, memory pools, etc. What makes this
a bug is that it is a surprise. It probably would have gone unnoticed
by me but for the operating system killing my testbed. :)
The need for this heap allocated vector appears to be packing related,
would it make sense to expose the packing algorithm as a free function
like the std::transform in <algorithm> instead? It could even take a
callable object, just like transform does (it'd be nice to reuse the
IndexableGetter there, if that's what it needs).
rtree::pack( srcBegin, srcEnd, packedBegin, packedEnd );
where srcBegin and srcEnd are random access, const_iterators and
std::distance(srcBegin,srcEnd) == std::distance(packedBegin, packedEnd).
Or an output iterator:
rtree::pack<Type, Type, Type>( srcBegin, srcEnd, packedIter );
Then the user would be responsible for allocating the packed container
and the resultant packing what would be passed in as a ctor (or a
factory method that has some sort of name that says "packed"):
auto rtree =
bgi::rtree<ValueType,Partitioner,Indexer>make_packed_rtree(packedBegin,
packedEnd);
// Or, the constructor
auto rtree = bgi::rtree<ValueType,Partitioner,Indexer>(packedBegin,
packedEnd);
That gives the flexibility of allocation without compromising the API.
I think it is cleaner to make a bulk loaded rtree construction more
explicit (vs. insert) and it removes the "surprise" of allocation that
packing requires.
>
> But would it solve your problem?
Yes. My test of 50,000,000 points died because it ran out of memory
(this is a "small" test). It was a big surprise to see that the rtree
needed to allocate outside of the allocator and not use the functor to
derive what it needed. I'm not focused on persistence, that was a means
to an end. My overall goal is to give my users the query ability of
data too large to fit in memory. If the rtree only stored the ValueType
as implied in the documentation and only used the allocater, as implied
by the API...
>
> Alterntively a second allocator could be passed for this temporary
> container, so a second, temporary file could be used. This would
> probably be the most convenient for you, am I right? However this
> would require to complicate the interface (constructors) so I don't
> like it.
I agree that putting yet another allocator in the constructor makes it
even more complex than it should be. Does the rtree really need to keep
the centroids of all of the data while it is packing? Couldn't those be
derived from calling the passed in IndexableGetter? If not, then maybe
getting the centroid is fundamental enough to deserve its own functor,
or a some other way to model that supports indexing, finding the
centroid and equality?
If the packing algorithm really needs the temporary storage, then I
think that the constructor is doing too much and the functionality that
is packing should be made a free function and the rtree's constructor
made simpler.
>
> We should definietly think about it when implementing a "proper"
> persistance support.
Yeah, persistence support is another thing entirely. I'm talking about
the happy case of memory based allocation right now - rtree is not
honoring its API contract with regard to allocators. The harder problem
of persistence is another story, but yes, that would be grand to have
all that too!
I'll take a look to see if I can't figure out if any of my ideas make
any sense. I don't know the domain well, but I do have a lot of C++
experience. I'll let you know either way.
Best,
Tim