Hello. I just successfully passed my bachelor. The theme of my bachelor degree was compare performance of all containers included in STL library. I selected to test it with STLPort and Microsoft STL. Now I have some things which should be improved in STLPort. Everything has been measured with "new" allocator to exactly detect allocated memory and to have all condition for both STLPort and Microsoft STL.
STLPort has much better performance in all standard operation with all containers.
1) Why "slist" allocates the same amounto of memory as "list"? Shouldn't slist eat less memory due to absence of pointer to next element (it has only pointer to previous element) ?
2) Microsoft STL has faster insertion to "list" (using "insert")
3) I developed my own hash table. It provides only simple operation - insert, remove, find, size, empty. Its size is based on prime numbers taken from STLPort's hash table. The allocated memory is exactly same bytes as in STLPort. But object size is only 12 bytes (STLPort has 28 bytes) and it is much faster than hash_map or unordered_map in STLPort. It would be nice if you could review the code and try improve performance of STLPort's hash table.
If you are insterested, I can provide my HashTable's source code or provide some more information.
This is interesting, thanks for your effort. What STLport version have you try ? and what MSVC version too ?
1) Maybe this is due to memory alignment issue, when you ask for N bytes the system has to give you at least N bytes but it can give you more... what is sure is that on a design point of view STLport is requesting less memory for slist than for list.
2) Good to know but 'why' would be more interesting.
3) This is why knowing which STLport you use is important. In latest versions hashtable has been completely rewritten, major of issue of previous version was that moving through all hashtable elements was requiring computation of hash functions. Does your implementation meet the (future) C++ Standard requirements ? when you are talking about object size do you mean sizeof(unordered_set<int>) for instance ? If so it is not really important because hashed containers are design to contain a lot of values, saving 16 bytes won't change a lot.
The complete testing was done on 6th April 2008, so I was using STLPort SVN which was available at that time. If you have made some other changes to STLPort's hash table, I could do new test to see changes. MSVS 2008 Professional.
I can also test slist/list memory usage with alignment set to 1 byte to see if it helps.
My hashtable implementation is available here: http://www.home.karneval.cz/01027053/tmp/HashTable.h
(just ignore Czech comments ;-)
The default hash function is simple casting key to size_t which looks enough for me.
Yes, I mean sizeof as object size. The one of reasons I made this hashtable is smaller object size, because I need to create really many objects with hashtable (instances of users where their data are stored to hashtable) in my application and need to save so much memory as possible. So, when I create 100 000 instances, it will eat about 2.8 MB RAM with STLPort's hashtable, but my implementation will eat only about 1.2 MB RAM. I know, it's not big difference nowadays, but my application has to be executed also on older PC with low RAM and this is the final phase of optimizations.
Looks like specialized container; a little chance that it applicable in 'standard' practice.
I found a bug in my implementation. It didn't work with pointers, so I've updated the code and now it works correctly. Uploaded here http://strongdc.sourceforge.net/common/HashTable.h because previous FTP doesn't work now.
I made a new inserting test of my HashTable vs STLPort's unordered_map. Inserting pair<int, int> to my hashtable is faster only little bit, but when inserting pair<char*, char*> it is about 100x faster than unordered_map.
btw, I use my HashTable in all application as it would be classic STL container, so I don't think it is specialized.
Sorry but your proposition is definitely not a proposition for a C++ Standard unordered container implementation. The major reason because it is smaller is that there is not:
- load factor
- stored hash functor instance
- stored equal functor instance
- stored allocator instance
Have you try to explain the difference between int and char* benchmarks ? Is it your implementation that is 100x faster in inserting pair<char*, char*> than pair<int, int> or is it STLport that is 100x slower in inserting pair<int, int> than pair<char*, char*>. I hope it is the first proposition because type of stored element shouldn't have impact on algorithmic complexity. The only explanations I can think about are:
- The hash functor for int is much better than the hash functor for char*
- The int values you used for your bench are more evenly distributed that the char* values
Sign up for the SourceForge newsletter:
You seem to have CSS turned off.
Please don't fill out this field.