Google: B-Tree Containers!
-
Hello, guys. I will say nothing, just a link: http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html
Let's port Qt containers to usage of them!
-
Seems like a good idea.
-
[quote author="Thomas Zander" date="1360180816"]Would be interesting to see a comparison with those and the Qt ones.
I know the stl ones suck big time ;) Mostly due to absence of copy-on-write.[/quote]IIRC, current implementation uses red-black trees, so this B-tree stuff should be faster.
-
@Andre
Copy on write in Qt is implemented using a QAtomicInt, as such its as ready for multithreading as it can be.So I disagree with you, its actually much much easier to use COW based classes in Qt with multithreading. Its the actual class you are using that typically is not fully multithreading safe. A QList is not, for instance. But thanks to COW you can have a shallow copy of your QList with little to no overhead and have one copy in each thread.
In the STL world you also have to make a copy, but thats expensive since its per definition a deep copy. -
I used "this":http://www.gotw.ca/publications/optimizations.htm as my source.
-
@Andre;
the article is kinda old, which may explain the problem. Its hooking in on a problem in an average COW implementation back then. That problem has since been solved.
He writes this (no longer correct) point;
"[COW] always forces the string class to incur some overhead, but in practice the
overhead can be disastrously expensive if the implementation additionally incurs
needless inefficiencies."Since then we got atomics in practically all CPUs and Qt uses that. Next to that its smart to avoid a check when using const methods (since they are non-write).
Bottom line is that making a class use COW is practically free when using it normally :)
-
@Thomas:
Thanks for your input. I appreciate it.Slightly off-topic: on the const thing in the context of threads and C++11, I recently spotted "this video":http://channel9.msdn.com/posts/C-and-Beyond-2012-Herb-Sutter-You-dont-know-blank-and-blank by Herb Sutter. Interesting stuff!
-
Thanks for the links and the information!
