Re: [boost] Boost library submission (poll for interest)
On Jan 5, 2010, at 9:08 AM, Ion Gazta?aga <igaztanaga@gmail.com> wrote:
I think most in-memory databases use T-trees as main containers. I plan to add them as Interprocess containers for late 2010, but of course, that will depend on my free time. With those containers, we could speed up searches and waste less space.
Would the interface remain identical to map? The current 'trans_map' can be revised slightly so that it would be a transactional wrapper for any map implementation, leaving the internals of storage to the implementation. Taking advantage of a T-tree variant would then be very easy to accomplish. One of the biggest challenges I'm seeing with high throughput on map is that operations like insert() and erase() cannot be done to concurrently by multiple threads, and consequently those operations become a bottlneck. I'm doing operations like find() and updates (to different entries) in parallel. A map implementation which internally segmented itself into sections under independent mutexes in order to permit highly concurrent modifications of any kind would be a big help. Anyone know of any such implementations? - Bob
Am Wednesday 06 January 2010 02:18:50 schrieb Bob Walters:
One of the biggest challenges I'm seeing with high throughput on map is that operations like insert() and erase() cannot be done to concurrently by multiple threads, and consequently those operations become a bottlneck. I'm doing operations like find() and updates (to different entries) in parallel. A map implementation which internally segmented itself into sections under independent mutexes in order to permit highly concurrent modifications of any kind would be a big help. Anyone know of any such implementations?
any implementation based on shadowpaging, e.g. this open source one: http://1978th.net/tokyocabinet/ I don't know any internals of Berkeley DB, but it also supports concurrent modifications. the containers I describe here: https://svn.boost.org/svn/boost/sandbox/persistent/libs/persistent/doc/html/... also support concurrent modifications, since their container nodes are implemented as MVCControlled objects. but they are much less efficient in absolute terms than a low-level container implementation.
El 06/01/2010 2:18, Bob Walters escribió:
On Jan 5, 2010, at 9:08 AM, Ion Gazta?aga<igaztanaga@gmail.com> wrote:
I think most in-memory databases use T-trees as main containers. I plan to add them as Interprocess containers for late 2010, but of course, that will depend on my free time. With those containers, we could speed up searches and waste less space.
Would the interface remain identical to map? The current 'trans_map' can be revised slightly so that it would be a transactional wrapper for any map implementation, leaving the internals of storage to the implementation. Taking advantage of a T-tree variant would then be very easy to accomplish.
Yes, it would be identical, except that you have different iterator validation guarantees, because a T-tree instead of nodes has arrays and that requires some copying (or moving) when rebalancing. So iterators might be invalidated when inserting or erasing. Is that a problem for your library. Best, Ion
Ion, while we're discussing persistent containers, could you please have a look at the following patch to Boost.Intrusive and tell me if you'd be ok with these changes? https://svn.boost.org/svn/boost/sandbox/persistent/libs/persistent/src/intru... The containers described here require the patch: https://svn.boost.org/svn/boost/sandbox/persistent/libs/persistent/doc/html/... the patch does: - remove some assumptions/restrictions, which should not have any effect on existing code using Boost.Intrusive (e.g. the assumption that Container::pointer is always a C++ pointer) - expose the container's header/root node through a "protected:" interface to its derived class. the changes are currently only made to those Boost.Intrusive containers that I use, but if you want them uniformly applied to all containers I can do that. thank you, Am Wednesday 06 January 2010 17:18:50 schrieb Ion Gaztañaga:
El 06/01/2010 2:18, Bob Walters escribió:
On Jan 5, 2010, at 9:08 AM, Ion Gazta?aga<igaztanaga@gmail.com> wrote:
I think most in-memory databases use T-trees as main containers. I plan to add them as Interprocess containers for late 2010, but of course, that will depend on my free time. With those containers, we could speed up searches and waste less space.
Would the interface remain identical to map? The current 'trans_map' can be revised slightly so that it would be a transactional wrapper for any map implementation, leaving the internals of storage to the implementation. Taking advantage of a T-tree variant would then be very easy to accomplish.
Yes, it would be identical, except that you have different iterator validation guarantees, because a T-tree instead of nodes has arrays and that requires some copying (or moving) when rebalancing. So iterators might be invalidated when inserting or erasing. Is that a problem for your library.
Best,
Ion _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Bob Walters -
Ion Gaztañaga -
Stefan Strasser