Re:Google paper comparing performance of C++, Java, Scala, a...
by acqq on Friday June 03, 2011 @04:30AM
(#2615574)
Exactly. Using hash maps and vectors are really elementary choices. Can you consider understanding enough in "systems programming" (see other comments for definition) without knowing that hash_map is implemented using hash tables and map using a tree? And that therefore adding elements to the map would incur rebalancing costs which hash_map wouldn't, as soon as you can estimate the number of elements to be processed. I consider it more a "meta" than a "language" decision.
Re:Google paper comparing performance of C++, Java, Scala, a...
by scott_s on Friday June 03, 2011 @11:05AM
(#2616607)
Rather than library knowledge, I submit it's basic algorithmic and data structure knowledge. Perhaps one could argue it's knowing how that algorithmic and data structure knowledge maps to actual libraries.
By the way, std::list::size() is defined to be O(1) (see http://www.kuzbass.ru:8086/docs/isocpp/lib-containers.html#l...). While it's possible, of course, to define a linked-list where the size operation is O(n), that's not an implementation of std::list. Hence, there was no difference when std::list::empty() was used - although I agree it's better to use it, since it's more meaningful.
Re:Google paper comparing performance of C++, Java, Scala, a...
by davidtgoldblatt on Friday June 03, 2011 @01:49PM
(#2617278)
In a confusing bit of ISO trivia, std::list implementations can do either - the standards draw a distinction between "should" and "shall". If an implementation "shall" do something, it's a requirement, and if it "should" do something, it's the preferred choice among several. The size() function only "should" be constant time. In fact, in GCC (which I assume is the Google compiler of choice), std::list::size() is O(n) (http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a0142...).
In fact, looking at the list of optimizations on page 9, the only one that involved a low-level understanding of the machine and resulted in a significant improvement was (unless I missed something) the use of InlinedVector (and this is only barely such a case - lots of C++ codebases have a similar class).