container performance on 64 bit systems
Hi, This may seem slightly off topic initially but bear with me. I have recently been having fun with the ordinary STL containers on a 64bit linux system. In particular the sorted associative containers set and map bloat the memory usage to an unacceptable level. Part of this is down to 64 bit pointers versus 32 bit pointers. In a standard Red-Black tree implementation each node has 3 pointers, these double in size as do any pointers in the containers themselves. There are also issues with allocating on 8byte and 16byte boundaries. I measured and discovered that an otherwise highly efficient structure took *10* times as much memory on a 64bit machine vs. the 32bit one. I can half the memory usage for a std::set by replacing it with a std::vector and sorting it manually. Nothing too out of the ordinary there. To solve my problem I have replaced a large number of 64bit pointers with indices and manipulate std::vector's of these instead of using associative containers. Are there any 'better' implementations of std::set etc. (preferably open source GNU/Linux compatible) out there? Are any planned? Does boost contain any suitable replacements? Does boost itself suffer from or tackle this 64bit bloat problem? Regards, Bruce. ____________________________________________________________________________________ Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it's updated for today's economy) at Yahoo! Games. http://get.games.yahoo.com/proddesc?gamekey=monopolyherenow
I've had the same problem. I ended up writing a key-based binary-sorted vector. Same storage as a normal vector, but sorted and it's a bit faster than a std::map. Damien _____ From: Bruce Adams [mailto:tortoise_74@yahoo.co.uk] To: boost-users@lists.boost.org Sent: Fri, 21 Sep 2007 10:24:58 -0600 Subject: [Boost-users] container performance on 64 bit systems Hi, This may seem slightly off topic initially but bear with me. I have recently been having fun with the ordinary STL containers on a 64bit linux system. In particular the sorted associative containers set and map bloat the memory usage to an unacceptable level. Part of this is down to 64 bit pointers versus 32 bit pointers. In a standard Red-Black tree implementation each node has 3 pointers, these double in size as do any pointers in the containers themselves. There are also issues with allocating on 8byte and 16byte boundaries. I measured and discovered that an otherwise highly efficient structure took *10* times as much memory on a 64bit machine vs. the 32bit one. I can half the memory usage for a std::set by replacing it with a std::vector and sorting it manually. Nothing too out of the ordinary there. To solve my problem I have replaced a large number of 64bit pointers with indices and manipulate std::vector's of these instead of using associative containers. Are there any 'better' implementations of std::set etc. (preferably open source GNU/Linux compatible) out there? Are any planned? Does boost contain any suitable replacements? Does boost itself suffer from or tackle this 64bit bloat problem? Regards, Bruce. ____________________________________________________________________________________ Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it's updated for today's economy) at Yahoo! Games. http://get.games.yahoo.com/proddesc?gamekey=monopolyherenow _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, Sep 21, 2007 at 09:24:58AM -0700, Bruce Adams wrote:
In a standard Red-Black tree implementation each node has 3 pointers, these double in size as do any pointers in the containers themselves. There are also issues with allocating on 8byte and 16byte boundaries.
A thought that just occured to me: *if* STL allowed parametrization over pointer types (as it allows with allocators now), you could use system- specific routines to allocate memory in lowest 4GB of address space and still have 32-bit pointers. The 'pointer class' would take care of converting 32-bit value to proper 64-bit pointer. It wouldn't have to be pointer either, but e.g. array index or something else (accessor that walks to disk and maintains in-memory cache). Which reminds me, you might want to look at http://stxxl.sourceforge.net/ [I have never personally used it]
participants (3)
-
Bruce Adams -
Damien Hocking -
Zeljko Vrba