Geometry Boost List: Re: [geometry] 1.57 Storing indices as values to save space.

Subject: Re: [geometry] 1.57 Storing indices as values to save space.
From: Tim Finer (tim.finer_at_[hidden])
Date: 2014-11-26 14:30:37

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.

Best,
Tim

On 11/26/14, 10:37 AM, Tim Finer wrote:
> Hi Adam,
>
> I'm trying yet another approach, heh.  This time with 1.57.
>
> I'm going to see if I can't just store the spatial data in a memory 
> mapped vector and indices into it in an in-memory rtree, as long as I 
> relax my requirement for the size of the data a bit.
>
> What I thought I'd try is storing the smallest sized unsigned integer 
> index possible (given the data) and reference a shared memory that I 
> control the layout of.  As a test, I set up an rtree with the value of 
> std::uint32_t and passed in an IndexableGetter functor that returns an 
> indexable double triplet when it receives the std::uint32_t value.  I 
> used the packing constructor to minimize the memory footprint.  This 
> all works, except, it looks like the rtree really stores a pair of an 
> indexable point and a value and not just the values.
>
> I did some before and after memory snapshots and determined the size 
> of the memory used is the same regardless if I set the value to an 
> index, or if I fill the rtree with the double triplets directly.  My 
> expectation was that the functor would be used each time that the 
> indexable is needed, because the documentation said "Important: The 
> translation is done quite frequently inside the container - each time 
> the rtree needs it".
>
> Except, that isn't really the case.  What really happens is that the 
> rtree caches a temporary vector of the entire size incoming data.
>
> pack_create.hpp, around line 155:
> std::vector<entry_type> entries;
> entries.reserve(values_count);
>
> Where entry_type is a std::pair<point_type, InIt>, where 
> sizeof(point_type) is 24 and InIt is the incoming value iterator.
>
> I also tried dynamically inserting nodes too, but that used even more 
> memory, although I didn't spend too much time looking at why.
>
> So my question is, what is the purpose of the IndexableGetter?  Is 
> there a way to trade off speed for space such that the rtree uses an 
> IndexableGetter all the way through?  Was this by design?
>
> Best,
> Tim