[Development] B-Tree containers instead of STL in Qt

[jamey.hicks at nokia.com]

Hi Illya,

I think it is an interesting idea to try B-Trees as an alternative to other search trees for in-memory data structures. As with any data structure, you have to consider the circumstances in which they perform better than an alternative. These days, caches are so large and DRAM latency has grown to quite a few CPU cycles, so it would not surprise me if there are cases where in-memory B-Trees perform better because the search would get to make more comparisons per cache line fetch.

There is a Qt module that was under development that uses B-Trees: Qt Json Db, but its B-Trees were all designed to index non-volatile secondary storage so I do not know if it would be helpful to you.

If you are interested in pursuing B-Trees for Qt applications, I would recommend defining an interface similar to QMap and doing some performance tests to characterize if/when it performs better. There is an advantage to being able to swap one container structure for another without rewriting the code using the container.

Cheers,
Jamey



On Feb 8, 2013, at 3:51 AM, ext Illya Kovalevskyy <illya.kovalevskyy at gmail.com<mailto:illya.kovalevskyy at gmail.com>> wrote:

Hello.

I found one Google thing, a useful thing - http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html. According to benchmarks: they are faster than STL containers.

Afaik, Qt uses STL containers in its QVector, QMap, etc. Maybe it's a good idea to port it to usage of B-Tree containers, is it?

--
Happy Coding,
Illya Kovalevskyy

_______________________________________________
Development mailing list
Development at qt-project.org<mailto:Development at qt-project.org>
http://lists.qt-project.org/mailman/listinfo/development

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20130211/0d61565d/attachment.html>