Geometry Boost List: Re: [geometry] Storage allocator questions

Subject: Re: [geometry] Storage allocator questions
From: Tim Finer (tim.finer_at_[hidden])
Date: 2014-11-29 14:03:46

Hi Henry,

On 11/29/14, 10:48 AM, Henry Roeland wrote:
> Hi Adam,
>
> It would be greet if I can focus on storage allocator and leave the 
> rtree part to you or somebody else.
>
> I hope I can still ask you guys questions concerning this storage 
> allocator? I have some global Idea's and probably need help both on 
> design level and implementation.
>
>
> Questions so far:
>
> 1. Is paging the only mechanism to get memory growth under control for 
> an rtree? Its the only one I can think of, but maybe there are other 
> ways to explore?
>
>
> 2. Is there any way an rtree can be read-only? Or set read-only after 
> (bulk)insert?
>
>
> 3. One problem/challenge is how to get and keep region(box) 
> coordinates "divided" over the page nodes. At least thats my 
> understanding of an (r)tree. You need the region coordinates as fast 
> lookup ID to know if a query should "dive" into the page or its sub 
> pages or not.
> Crazy idea: Maybe the allocator should manage an rtree of pages with 
> references/pointers to the "real" tree nodes?
>
> Questions:
>
>   * Is my understanding of data lookup right? So coordinates determine
>     the location of the data inside the RTree?
>   * If this is true does this then mean that all Pages (Loaded or
>     unloaded) must be known including its region coordinates?
>   * This in order to get/keep the tree balanced and know which page
>     must be loaded (by coordinate query)?
>
>
> Lets discuss the different actions an storage allocator can/must handle:
>
>   * Load in Page data on request by RTree
>       o "Load" can mean anything: From File, From DB, From
>         MessageQueue,...
>       o "Request" means query hits coordinate region that matches the
>         Page coordinates
>   * Bulk Load multiple pages at once???
>
>
>   * Unload Page data on request by Storage Manager itself(?)
>       o "Unload" can mean:
>           + To /dev/null :-) Only useful when read-only rtree
>           + To File: Memory mapped or otherwise
>           + To DB: Save data to (spatial) database
>           + To MessageQueue
>           + ???
>       o "Request" can mean:
>           + Smart_pointer(s) say that nodes inside page are not used
>             anymore
>           + Smart_pointer(s) say that page is not used anymore
>           + Amount of usage(hit count) is small
>           + ???
>   * Bulk Unload multiple pages at once???
>
>
> NOTE: The storage allocator must, as Adam already pointed out, deliver 
> an interface to make above points possible. But not implement them in 
> anyway.
>
> Other questions/points that come to my mind are:
>
>   * Must the storage allocator always store? What about transactions
>     between in memory (RTree) and Persistence storage?
>   * State-full allocator: Who owns the nodes and the data inside it? I
>     always thought of an allocator like a factory that does not own
>     the data...
>   * When data is owned by another STL(like) container then IMHO a
>     storage allocator has no use. This because the storage allocator
>     then does not own the data and has no means to free/unload it.
>
>
>
> Above is going top down by requirements/features but code-wise I will 
> try to handle in my next e-mail.
>
> Thanks for your time,
>
> Kind regards,
>
> Henry Roeland
>
>
>> On 26 nov. 2014, at 22:12, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden] 
>> <mailto:adam.wulkiewicz_at_[hidden]>> wrote:
>>
>> Hi Henry,
>>
>> Henry Roeland wrote:
>>>
>>>> On 26 nov. 2014, at 17:48, Adam Wulkiewicz 
>>>> <adam.wulkiewicz_at_[hidden] <mailto:adam.wulkiewicz_at_[hidden]>> wrote:
>>>>
>>>> Henry Roeland wrote:
>>>>> Dear all,
>>>>>
>>>>> First let me introduce myself: my name is Henry Roeland 37 years 
>>>>> old and currently working as software engineer for a company that 
>>>>> delivers maps to car companies like BMW and VW.
>>>>> I'm working in the testtools team that is responsible for a map 
>>>>> viewer and maptest batch tool.
>>>>> Technics that we use are C/C++, Sqlite, spatialite and of corse boost.
>>>>>
>>>>> Personally I have multiple years of C++ experience and busy 
>>>>> getting up to speed with geometry technics in 2D. NeXT to that 
>>>>> just started with studying advanced datastructures and algoritms 
>>>>> like b+tree and r*tree.
>>>>>
>>>>> Currently I see your rtree as a perfect candidate for in memory 
>>>>> container/index/cache in our map interface. As I wrote in my 
>>>>> previous email the feature that is not supported yet is paging. 
>>>>> How can I help to accomplish this feature? Are there specs? Or am 
>>>>> I the only one in favior of this feature?
>>>> Certainly not the only one. People are asking about it from time to 
>>>> time, using Interprocess' mapped file as a replacement. You're the 
>>>> only one who is willing to help with the implementation. I greately 
>>>> appreciate it.
>>>>
>>>>
>>>> As I mentioned before I was thinking about a stateful 
>>>> allocator/storage/manager handling file or files/pages, cacheing 
>>>> etc. This allocator would return pointers which when dereferenced 
>>>> would force the allocator to load and cache data. Then, there would 
>>>> be a mechanism to tell the allocator that some pointers/data aren't 
>>>> used anymore. It could be done explicitly by calling some function 
>>>> on allocator like:
>>>>
>>>> persistent_allocator alloc(...);
>>>> rtree<..., persistent_allocator> rt(..., alloc);
>>>>
>>>> rt.insert(...);
>>>> rt.insert(...);
>>>> rt.insert(...);
>>>> alloc.flush();
>>>>
>>> I don't know about an rtree but from my homework:-) concerning 
>>> b-trees I understood that pages can be handled as nodes themselves. 
>>> Pages can be split and contain multiple nodes depending on size. If 
>>> we could create a stable interface for Page(Nodes) then this 
>>> interface can become public leaving the Node interface hidden???
>>> It can also have other advantages to alloc a group of nodes (Page) 
>>> together in terms of memory alignment(Your don't need a smart 
>>> pointer for every node only for the page?), Also in terms of 
>>> (de)serialisation and bulk load handling a group of nodes would IMHO 
>>> be better (if its possible).
>>
>> Of course you're right, nodes could (or even should) be grouped in 
>> pages, loaded together etc. Also we should probably group close nodes 
>> together in one page (e.g. parents with children), allocator hint 
>> could be used for this. But I was thinking about leaving the desicion 
>> how to store nodes to the allocator/storage. As you said one could 
>> use big pages, one could store 1 node per file, or a database etc. 
>> And still somehow a page or some other storage or Archive must know 
>> what data should be saved/loaded per node. In my scenario this would 
>> just be implemented in a Serialization-like way. Higher level aspects 
>> like pages would be closed in allocator/storage. Of course assuming 
>> that this could be done this way but I feel that it could.
>>
>> I think that a pointer still would have to store some ID of a node 
>> inside a page to identify an exact placement of the data. Or at least 
>> some global ID somehow indexed to access a specific node in a 
>> specific page.
>>
>>>
>>>> The next step could be adding of some hooks or traits for 
>>>> allocators which would be called by the rtree internally on the end 
>>>> of some operation, e.g. insert. So this wouldn't be a C++ allocator 
>>>> anymore since it'd have additional methods.
>>>>
>>>> To avoid storing a reference to allocator/storage in those smart 
>>>> pointers the rtree could notify the allocator/storage when a 
>>>> pointer is dereferenced and data is required. So the responsibility 
>>>> for the notification of allocator/storage would be moved from a 
>>>> pointer to the rtree.
>>>>
>>> The Page Node can administrate its size and its free size and have a 
>>> smart_pointer telling when it was last used and dependency_checker 
>>> /unload checker with responsibility for notification. Maybe we can 
>>> use Boost Signals2 for notification?
>>>
>>>
>>> Together with a Page/Storage manager I'm thinking about the 
>>> following points:
>>> - Policy for when to load/unload. traits as you point it out.
>>> - Size of rtree must be known at all times. If some limit is reached 
>>> start unloading (allocator can tell the size?) to bottom pages that 
>>> are less used?
>>> - 25%/50%/75% percent of the top of the tree must remain in memory 
>>> for speed???
>>> - define 3 actions/states for a page: loaded, unloaded, unloaded but 
>>> cached as memory map.????
>>
>> So what you're describing here is how a paging allocator/storage 
>> could work. Sure if the storage was notified by the rtree about the 
>> performed actions it'd be able to do whatever it needs, cache pages, 
>> store some kind of usage counter to know which pages are used most 
>> often, support various policies, etc.
>>
>> I was describing more low level stuff that would have to be 
>> implemented on the rtree side. Basically 2 things notifications for 
>> actions and an interface for serialization of nodes and rtree header. 
>> Or would you prefer if I handled it, that you could focus on the 
>> implementation of a specific allocator/storage?
>>
>> There is also another thing that is mentioned in another thread 
>> (started by Tim). There should be some way of creation non-rtree, 
>> temporary pages, e.g. for data stored in a vector or some other 
>> container designed specifically for this purpose. But this could be 
>> handled later.
>>
>>>
>>>> Finally the rtree could notify the allocator/storage each time the 
>>>> data owned by a pointer is no longer needed but this probably 
>>>> wouldn't change anything. Furthermore modifying and releasing the 
>>>> nodes before an operation is finished wouldn't be safe in case when 
>>>> an exception was thrown. In fact, this allocator should keep a copy 
>>>> of nodes in memory during a whole operation and then at the end of 
>>>> the operation save the data into a persistent storage.
>>>>
>>>>
>>>> The next thing is how to serialize data from and to node. We should 
>>>> ask ourselves should we allow the users to implement other 
>>>> persistent storage variants on their own. If the answer was no, 
>>>> then we could just internally in the persistent allocator use the 
>>>> internals of the rtree. But if we wanted to allow it (which IMO 
>>>> should be done) the most straightforward way would be to expose the 
>>>> interface used by the rtree internally to access node's elements. 
>>>> Exposing it would mean that we couldn't change it in the future, so 
>>>> I'd prefer to avoid it. Instead, we could mimic or directly use 
>>>> Boost.Serialization interface for Nodes. In this scenario a 
>>>> specific Node would know what data must be saved and loaded and 
>>>> it'd be able to save or load to/from some generic Archive. 
>>>> Depending on the needs this could be some temporary 1-node Archive 
>>>> gathering data for later or a target Archive capable to serialize 
>>>> data on the fly, it'd depend on an allocator/storage.
>>>>
>>>> This way we could also support versioning on a node level, the same 
>>>> way how it's done in Serialization. So changes would have to be 
>>>> done on a nodes level not in the user-defined allocator. An example 
>>>> could be an implementation of a rtree variant storing additional 
>>>> data in nodes (hilbert r-tree) or additional types of nodes 
>>>> (PRtree). Also arbitrary user-defined Values would be serialized 
>>>> the same way (using Serialization or familiar Serialization-like 
>>>> interface).
>>>>
>>>> And this way we'd also support Serialization in one go.
>>>>
>>>>
>>>> We'd probably need some file header with the parameters of an rtree 
>>>> both in persistent storage and in serialization support. Similar as 
>>>> with nodes, an rtree could know how to load/save the header from/to 
>>>> some Archive. The rtree should e.g. check if it's possible to use 
>>>> persistent storage and load data, e.g. if it wasn't created using 
>>>> incompatible parameters, etc.
>>>>
>>>>
>>> How is it with backwards compatibility? I can imagine that Storage 
>>> work can break something already running?
>>
>> I think that this won't be problematic.
>>
>>> If I'm talking rubbish just tell me I can handle it:-)
>>>
>>
>> All ideas are valuable :)
>>
>>> Thanks for beneath info to getting me started. I will have to read 
>>> it a few times to understand it all.
>>
>> If you have any questions just ask. If I handled it on the rtree side 
>> and you was working on the allocator/storage, you probably wouldn't 
>> even be forced to know all of this internal stuff. Not that I have 
>> something against it :)
>>
>> Regards,
>> Adam

I have a request that the allocator be the sole source of allocation.  
One of my problems with the current implementation is that one of the 
constructors creates a temporary vector of centroids as a source for a 
packing algorithm.  My understanding is that the allocator needs to be 
generic enough to offer up a temporary buffer (something similar to 
std::get_temporary_buffer) so that the packing algorithm can take 
advantage of it without going to the heap.

Best,
Tim