[Mono-dev] ToString() performace in Mono revisited

Eyal Alaluf eyala at mainsoft.com
Mon Dec 31 07:23:42 EST 2007


Hi, all.

Thanks for the feedback. The amount of used memory is indeed not
appropriate for small devices and is not economic enough.

The 'DblExpTab' is essential in order for the double ToString to be
efficient.
As for the other two arrays they cache a simple arithmetic caclcualtion.

I'll therefore eliminate the '_decHexLen' array and use
  static readonly int[] _decHexDigits = new int [100];
I'll make DblRep into a struct and remove one member out of it (and
slightly improve the double.ToString() perf along the way).
This will change the allocation size to 100 * 4 + 2048 * (3 * 4) = ~25K.

The performance impact is betweek 3-10% overall for simple ToString()
depending on the hardware.

Eyal.

-----Original Message-----
From: Juraj Skripsky [mailto:js at hotfeet.ch] 
Sent: 30 December 2007 19:34
To: Atsushi Eno
Cc: Eyal Alaluf; Miguel de Icaza; mono-devel-list at lists.ximian.com
Subject: Re: [Mono-dev] ToString() performace in Mono revisited

Hello,

I think the following two arrays account for most of those 300KB:

static readonly int[] _decHexDigits = new int [10000];
static readonly int[] _decHexLen = new int [0x10000];

The first one consumes almost 40KB, the second one 256KB...

The "DblExpTab" array uses 2048 * 4 = 8KB and its referenced DblRep
objects 2048 * (8 + 4 * 4) = 48KB. This means a total of 56KB. Turning
DblExbTab into a struct would reduce this to 2048 * (4 * 4) = 32KB.

- Juraj


On Mon, 2007-12-31 at 00:19 +0900, Atsushi Eno wrote:
> Hello,
> 
> Kazuki pointed out that the static initialization part of
> NumberFormatter allocates 300KB. It is probably here:
> 
> 	public static readonly DblRep[] DblExpTab = new DblRep
[ExponentMax + 1];
> 
> It does not look good.
> 
> Atsushi Eno
> 
> 
> Eyal Alaluf wrote:
> > 
> > 
> > With the attchments zipped to reduce size.
> > 
> >  
> > 
> > * From: * mono-devel-list-bounces at lists.ximian.com 
> > [mailto:mono-devel-list-bounces at lists.ximian.com] *On Behalf Of
*Eyal Alaluf
> > *Sent:* 27 December 2007 17:28
> > *To:* mono-devel-list at lists.ximian.com
> > *Cc:* Miguel de Icaza
> > *Subject:* [Mono-dev] ToString() performace in Mono revisited
> > 
> >  
> > 
> > I got complaints that the font color within the table is white so
this 
> > is a resent J
> > 
> >  
> > 
> > Hi, all.
> > 
> >  
> > 
> > Attached is a redesigned implementation of the NumberFormatter
class. 
> > The patch includes a new algorithm for float and double ToString 
> > implementation that improves performance by a factor of 25(!) and
upto 
> > 440(!!!). The patch includes further improvements to integer
/ToString/ 
> > as well as Andreas suggestion of avoiding calling 
> > /NumberFormatInfo.CurrentInfo/ in the case of integer types default 
> > /ToString()/ implementation.
> > 
> > This patch should improve Mono's performance in important use cases
such 
> > as web-services where primitive /ToString/ performance is an
important 
> > factor.
> > 
> >  
> > 
> > The following is a table showing the improvements for the different 
> > primitive types using the patch. All the results are in milliseconds
and 
> > for a run of 10,000,000 iterations with warm-up of 10,000,000
iterations 
> > as well.
> > 
> >  
> > 
> >  
> > 
> > 	
> > 
> > Mono 1.2.6
> > 
> > 	
> > 
> > Patch
> > 
> > 	
> > 
> > Improvement
> > 
> > 12345.ToString("G")
> > 
> > 	
> > 
> > 10079
> > 
> > 	
> > 
> > 7328
> > 
> > 	
> > 
> > 1.37
> > 
> > 12345L.ToString("G")
> > 
> > 	
> > 
> > 13203
> > 
> > 	
> > 
> > 7297
> > 
> > 	
> > 
> > 1.81
> > 
> > 0.12345.ToString("G")
> > 
> > 	
> > 
> > 323750
> > 
> > 	
> > 
> > 13047
> > 
> > 	
> > 
> > 24.8(!)
> > 
> > 1.2345E-200.ToString("G")
> > 
> > 	
> > 
> > 6376500
> > 
> > 	
> > 
> > 14328
> > 
> > 	
> > 
> > 445(!!!)
> > 
> > 0.12345m.ToString("G")
> > 
> > 	
> > 
> > 51078
> > 
> > 	
> > 
> > 9875
> > 
> > 	
> > 
> > 5.2
> > 
> > 12345.ToString()
> > 
> > 	
> > 
> > 12406/7781
> > 
> > 	
> > 
> > 5687
> > 
> > 	
> > 
> > 2.2/1.37
> > 
> > 12345L.ToString()
> > 
> > 	
> > 
> > 15703/11016
> > 
> > 	
> > 
> > 5750
> > 
> > 	
> > 
> > 2.7/1.9
> > 
> >  
> > 
> > Note that for Mono 1.2.6 /12345/./ToString()/ there are two numbers
- 
> > the first is Mono 1.2.6 version (which is slower then 
> > /12345.ToString("G")/!) and the second is after applying Andreas 
> > suggestion on top of Mono 1.2.6.
> > 
> >  
> > 
> > The following are the results of the new algorithm compared to the
old 
> > Mono algorithm and the .Net 2.0 native ToString performance, all
three 
> > running on Microsoft .Net 2.0. The results show that the new code 
> > matches and even out-performs .Net /ToString/ implementation.
> > 
> >  
> > 
> > 	
> > 
> > Mono 1.2.6 algorithm
> > 
> > 	
> > 
> > Microsoft .Net 2.0
> > 
> > 	
> > 
> > New Patch algorithm
> > 
> > 	
> > 
> > Improvement over Mono 1.2.6
> > 
> > 	
> > 
> > Improvement over .Net 2.0
> > 
> > 12345.ToString("G")
> > 
> > 	
> > 
> > 3700
> > 
> > 	
> > 
> > 2291
> > 
> > 	
> > 
> > 1827
> > 
> > 	
> > 
> > 2.0
> > 
> > 	
> > 
> > 1.25
> > 
> > 12345L.ToString("G")
> > 
> > 	
> > 
> > 4559
> > 
> > 	
> > 
> > 2242
> > 
> > 	
> > 
> > 1919
> > 
> > 	
> > 
> > 2.38
> > 
> > 	
> > 
> > 1.17
> > 
> > 0.12345.ToString("G")
> > 
> > 	
> > 
> > 281090
> > 
> > 	
> > 
> > 4006
> > 
> > 	
> > 
> > 3897
> > 
> > 	
> > 
> > 72.1(!!)
> > 
> > 	
> > 
> > 1.03
> > 
> > 1.2345E-200.ToString("G")
> > 
> > 	
> > 
> > 5686000
> > 
> > 	
> > 
> > 4634
> > 
> > 	
> > 
> > 4613
> > 
> > 	
> > 
> > 1233(!!!)
> > 
> > 	
> > 
> > 1.00
> > 
> > 0.12345m.ToString("G")
> > 
> > 	
> > 
> > 14562
> > 
> > 	
> > 
> > 3095
> > 
> > 	
> > 
> > 2294
> > 
> > 	
> > 
> > 6.3
> > 
> > 	
> > 
> > 1.35
> > 
> > 12345.ToString()
> > 
> > 	
> > 
> > 3900/3002
> > 
> > 	
> > 
> > 2344
> > 
> > 	
> > 
> > 1313
> > 
> > 	
> > 
> > 3.0/2.3
> > 
> > 	
> > 
> > 1.79
> > 
> > 12345L.ToString()
> > 
> > 	
> > 
> > 4684/3823
> > 
> > 	
> > 
> > 2245
> > 
> > 	
> > 
> > 1383
> > 
> > 	
> > 
> > 3.4/2.8
> > 
> > 	
> > 
> > 1.62
> > 
> >  
> > 
> > It should be noted that the new code performance improvement are
even 
> > more visible on top of .Net.
> > 
> > It should also be noted that .Net runs the same algorithm 4 times
faster 
> > then Mono. Since this code is self contained and almost completely 
> > algorithmic - I believe that it may serve as a good practical test
case 
> > for improving Mono's JIT.
> > 
> >  
> > 
> > The redesign is composed of three main changes
> > 
> > *        An O(1) arithmetic transformation of a double (composed of 
> > sign, 2's exponent and mantissa bits) to sign, long and 10's
exponent.
> > 
> > *        Using a character array instead of a string buffer to
construct 
> > the string result.
> > 
> > *        Representing the number digits using hexadecimal values.
That 
> > is /12345/ will be represented by /0x12345/.
> > 
> >  
> > 
> > The patch passes Mono's unit tests on both 1.1 and 2.0.
> > 
> >  
> > 
> > Please review and provide us with your feedback as soon as possible.
> > 
> >  
> > 
> > Sasha, Roei & Eyal.
> > 
> > 
> >
------------------------------------------------------------------------
> > 
> > _______________________________________________
> > Mono-devel-list mailing list
> > Mono-devel-list at lists.ximian.com
> > http://lists.ximian.com/mailman/listinfo/mono-devel-list
> 
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
> 




More information about the Mono-devel-list mailing list