Re: Why is VC++ STL so slow?
Earl Purple wrote:
MariuszK wrote:
Could you write the simplest example when problem accure?
If problem accure only in map and set container I think that is
connected with container implementation.
Microsoft prefer implementation map with as hash_map (MFC CMap it is
hash_map). Generally hash_map is faster then normal map (finding time,
acces time etc.).
hash_map is a different type of map. It is nothing specific to
Microsoft. STL doesn't have a hash_map but there are several
open-source versions available, often provided as extensions
to STL.
Using big O notation, hash_map is faster as the number of
elements tends to infinity, because insertion is constant time
(i.e. it takes the same amount of time regardless of the
number of elements in the collection).
Insertion, but also find. And the "constant time" is only true
if you have a good hash function; degenerate hash functions give
linear time, and more or less poor hash functions will give
something between the two.
Constant time doesn't always mean faster than O( log N ).
Only as the size tends to infinity. For example, the constant
time could be 30. That means you'd need 2^30 elements (around
1 billion) before hash_map became faster.
Actual tests I did using GNU hash (some time back) show a break
even point of somewhere between 200 and 1000 entries. Even with
more entries, however, std::map is pretty fast, and I wouldn't
hesitate to use it up to 10000 or more entries.
But adding element to hash_map is slower.
Note that this statement is incorrect, as Earl pointed out
immediately before.
(It is connected
with hashing algorithm if you add many elements hashing
algorithm is called many times). Therefore, If you add
alements to hash_map first you should initialize size of
hash_map. Initialization is very important for hash_map.
Indeed hash_map is less scalable as you have to determine in
advance the size of your hash_map
Why? The hash_map in g++ doesn't require this, nor does the one
in VC++, nor the one I developped back in pre-STL days.
as well as a good hashing algorithm which will provide a
uniform distribution without taking the "constant"
hashing-time too high, but we are getting a bit off-topic
here.
Yes and no, since there will be a hash table (unordered_set,
unordered_map) in the next version of the standard (unless
something really wierd happens in the committee, to cause it to
be voted out after having already been accepted).
Good hashing algorithms are well known: FNV, for instance. If
you try to invent your own, you do run a risk, but if you use
one that has been proven effective, there should be no problem.
--
James Kanze GABI Software
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]