Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Is there in memory tree structure faster than std::map?

Reply
Thread Tools

Is there in memory tree structure faster than std::map?

 
 
Juha Nieminen
Guest
Posts: n/a
 
      08-14-2012
Melzzzzz <(E-Mail Removed)> wrote:
> Cache performance does not depends on allocator rather on how
> program accesses allocated blocks.


The speed of the allocator (from the perspective of the CPU caches) comes
into play if the program allocates and deallocates blocks very frequently.

Naturally if the program allocates memory in big bunches and then spends
a lot of time operating on that memory (without doing new allocations or
deallocations) then of course it depends on how the program uses that
memory (ie. how cache-local its operations are).

The thing is, doing a simple 'new' millions of times in a row (eg. to
create a big list or a set) can be horrendously slow. For example,
creating a list of ten million elements can take several seconds
(depending on the system, of course), 99% of that time being spent on
allocation alone, while creating a vector of ten million elements takes
virtually no time at all.

(I have noticed a significant improvement in relative allocation speed
(ie. in % of time spent in allocation as compared to everything else) when
using a 64-bit Linux in a 64-bit Intel system, as compared to a 32-bit
Linux running on a 32-bit system, which is cool. I don't know, however,
if this is caused by the hardware being more efficient or the 64-bit version
of the standard clib allocator being more efficient, or a combination of
both. It can still be annoyingly slow, though, although not that much
anymore.)

The lesson is: If possible, minimize the amount of allocations and
deallocations in your program.
 
Reply With Quote
 
 
 
 
Jorgen Grahn
Guest
Posts: n/a
 
      08-14-2012
On Tue, 2012-08-14, Juha Nieminen wrote:
> Jorgen Grahn <(E-Mail Removed)> wrote:
>> Unlikely because if I look at the Linux side of things, plenty of
>> programmers don't use threads, and intensely dislike threads. Seems
>> unlikely that they'd really tolerate a significant performance hit in
>> the C library for such a thing.

>
> Your argument why thread-safety in the standard allocator is unlikely to
> be a significant source of inefficiency is because lots of linux
> programmers don't like threads?
>
> That's actually one of the most hilarious arguments for *anything* that
> I have read in a long time.


You are easily amused. Software features are sometimes driven by user
requirements, are they not?

Anyway, that was just my explanation why I'm interested in your
results.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 1 10-30-2007 11:01 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
How to translate a C tree structure to ruby tree objects anne001 Ruby 1 02-18-2006 03:17 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments