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="sierdzio" date="1360145381"]Seems like a good idea.[/quote]
I will try to do it in a few days (weeks).
-
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 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]How my grandfather said, "Let's do it" :D
-
[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.
-
Copy-on-write is a nice mechanism in a single-threaded world, but that gets problematic soon in a multi-threaded one...
-
@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.
-
Can anyone help me with that? I've done some changes in qtbase. How can I run autotests and benchmarks tests for that?
I have qtbase repo cloned and some changes on HEAD.
-
@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!
-
I've discussed it with people on irc, and it looks like now it's not a very good idea, so, maybe we should wait with this.