Re: Performance of the default Node Allocator.

[Dhruv Matani <dhruvbird at gmx dot net>]

13.4   16.1    
On Wed, 2004-01-14 at 06:43, Loren James Rittle wrote:
> > I was talking about the performance of the default node allocator in
> > situations where the list is sorted, and the nodes get splayed about in
> > memory, and then subsequent allocations/deallocations suffer due to bad
> > cache performance. I have here a bitmapped allocator that attempts to
> > remove those defects. I'm attaching a driver program that shows the
> > performance of the default node allocator v/s the bitmapped allocator.
> 
> Interesting.  Based on description alone, your allocator sounds quite
> similar in design philosophy to that used by malloc(1) on FreeBSD.  It
> was explicitly designed with modern cache architectures in mind.
> 
> > You can see clearly that the bitmapped allocator not only allocates
> > memory faster, but also does not mess up the cache.
> 
> Actually, where is the data? ;-)

Oops! Here it is: ;-)

1). The default Node allocator.

[dhruv@home test]$ compile balloc_test.cpp -O3
[dhruv@home test]$ ./balloc_test 
Time Taken to Insert: 0.11 Seconds.
Size is: 550000
Time Taken to Sort: 1.22 Seconds.
Size is: 493251

Time Taken to Insert: 0.13 Seconds.
Size is: 1043251
Time Taken to Sort: 2.36 Seconds.
Size is: 0

Time Taken to Insert: 0.27 Seconds.
Size is: 550000
Time Taken to Sort: 2.19 Seconds.
Size is: 266020

3 //At this point, I do ps aux, and the memory consumption is 13.4% of
the 128 MB that I have.

2). The Bitmapped Allocator.

[dhruv@home test]$ compile balloc_test.cpp -O3
[dhruv@home test]$ compile balloc_test.cpp -O3
[dhruv@home test]$ ./balloc_test 
Time Taken to Insert: 0.12 Seconds.
Size is: 550000
Time Taken to Sort: 1.15 Seconds.
Size is: 493251

Time Taken to Insert: 0.11 Seconds.
Size is: 1043251
Time Taken to Sort: 2.14 Seconds.
Size is: 0

Time Taken to Insert: 0.11 Seconds.
Size is: 550000
Time Taken to Sort: 1.14 Seconds.
Size is: 266020

3 //At this point, I do ps aux, and the memory consumption is 16.1% of
the 128 MB that I have.

I think that the memory usage can be worked on, because currently, the
internal pool is set to grow exponentially until a certain thrteshold,
after which it remains conatant.


> > If anyone wants the
> > source, I can send it by email. You can see that the sort is twice as
> > fast in the bitmapped allocator compared to the default node allocator
> > when used repeatedly. Also, could anyone test out these things for me on
> > other platforms?
> 
> > Link to get the bitmapped allocator:
> > http://www.geocities.com/dhruvbird/nstl/nstl0.2.zip
> 
> What are your intentions on contributing this code to the FSF gcc?

I'm fine with it.

BTW, is anyone else facing CVS problems, am I the only person? And one
more thing. What is the equivalent of the bsf instruction on other
architectures.

> Regards,
> Loren
-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/