404824 - Expensive & unneeded calcs done in arena init

Status: RESOLVED FIXED

(NSPR :: NSPR, defect, P1)

Description

[Steve Snyder]

In PL_InitArenaPool() a lot of processing time is devoted to calculating a value that is known at build time.

This is the problem:

    pool->mask = PR_BITMASK(PR_CeilingLog2(align));

That PR_CeilingLog2() function is very expensive (though much less so with the x86 bitscan instruction from bug 356852) and is the bottleneck in arena pool initialization.

I find that PL_InitArenaPool() is called a *lot* when viewing a page of animated GIF images using the Mozilla 1.8.1.10 branch code.  And called ~6100 times in the course of bringing SeaMonkey 1.1.7 up to www.yahoo.com.

That it appears in profiling is due soley to calculating a value that is already known.

Comment 1

[Steve Snyder]

Attachment: For common cases, use look-up table, not Log2 calcs

Avoids (nearly?) all calculations of mask values at runtime by using a look-up table.  Mask values are still calculated in the unlikely event that the caller wants more than 32 bytes of alignment.

Comment 2

[:Gavin Sharp [email: [e-mail]]]

Steve, are you going to ask for review on the patch?

Comment 3

[Steve Snyder]

(In reply to comment #2)
> Steve, are you going to ask for review on the patch?

Who can I get to turn me down (ahem) on something like this?

Comment 4

[:Gavin Sharp [email: [e-mail]]]

(In reply to comment #3)
> (In reply to comment #2)
> > Steve, are you going to ask for review on the patch?
> 
> Who can I get to turn me down (ahem) on something like this?

I sense resentment! :( I hope your Mozilla contribution experiences haven't been all bad...

The active peers for NSPR are wtc and Nelson (Darin and cls are also listed at http://www.mozilla.org/owners.html#nspr but they're not actively involved in Mozilla development at the moment). wtc has CCed himself here so perhaps he would be interested in reviewing it.

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 289703 [details] [diff] [review]
For common cases, use look-up table, not Log2 calcs

Suggested improvements:

>-    if (align == 0)
>-        align = PL_ARENA_DEFAULT_ALIGN;
>-    pool->mask = PR_BITMASK(PR_CeilingLog2(align));
>+    /* input alignment value of 0 means the default value of 8 is used */

The old default value, PL_ARENA_DEFAULT_ALIGN, is defined as sizeof(double).
It that guaranteed to be 8 on all platforms?  At the very least, the comment 
should document the default as being PL_ARENA_DEFAULT_ALIGN, not merely "8".
Perhaps, rather than hard coding the default mask as '7' below, it would be
better to code it as PR_BITMASK(PL_ARENA_DEFAULT_ALIGN).  Same result, 
self documenting.

>+    /* incoming value of param "align" is typically 0, or 4, or 8      */
>+    static const PRUword pmasks[33] = 

Save 99 bytes (231 bytes on 64-bit CPUs) from that table by changing it from 
a table of PRUword into a table of PRUint8, and let the compiler promote the 
value in the assignment below.

>+        { 7, 0, 1, 3, 3, 7, 7, 7, 7,15,15,15,15,15,15,15,     /*  0 .. 15 */
>+         15,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}; /* 16 .. 32 */
>+
>+    if (align <= 32)
>+        pool->mask = pmasks[align];
>+    else
>+        pool->mask = PR_BITMASK(PR_CeilingLog2(align));

Maybe:
    pool->mask = (align <= 32) ? pmasks[align] 
                               : PR_BITMASK(PR_CeilingLog2(align));

Comment 6

[Steve Snyder]

Attachment: 2nd revision; addresses comments

Changes:

1. More comments, which I hope clarifies why the requested default alignment ends up being aligned on an 8-bytes boundary.  (Yes, doubles are always 8 bytes in length.  Works out nicely for 64-bit ints, too.)

2. Changed size of array elements to PRUint8 (from PRUword) to save a little memory, at the trivial cost of runtime promotion of data size.  Thanks, Nelson.

Comment 7

[Kai Engert (:KaiE:)]

is this ready for check in?

Comment 8

[Wan-Teh Chang]

Attachment: 3rd revision (as checked in)

Steve, thanks for the patch.  I avoided the assumption of
sizeof(double) == 8 by an extra if statement.  I also made
some minor (mostly coding style) changes.  I've checked in
this patch on the NSPR trunk for NSPR 4.7.

Checking in plarena.c;
/cvsroot/mozilla/nsprpub/lib/ds/plarena.c,v  <--  plarena.c
new revision: 3.14; previous revision: 3.13
done

Comment 9

[Wan-Teh Chang]

(In reply to comment #5)
> The old default value, PL_ARENA_DEFAULT_ALIGN, is defined as sizeof(double).
> It that guaranteed to be 8 on all platforms?

The C Standard doesn't have a requirement on the absolute
minimum size of double.  Almost all C implementations today
use IEEE floating point standard, in which a double-precision
floating point number is 64 bits.  This is why sizeof(double)
is 8 in practice.

Brendan, I believe you're the original author of PRArena.
Do you think we can just define PL_ARENA_DEFAULT_ALIGN as 8,
with no reference to the size of double?  If so, in the
patch (attachment 297925 [details] [diff] [review]) we can initialize pmasks[0] to 7
(the value of pmasks[8]) as Steve's original patch did
(attachment 291032 [details] [diff] [review]).

Back when the original code was written (1995-1996), double
was probably the only standard C type that's 64-bit, and was
probably the largest standard C type (64-bit platforms were
uncommon).  I suspect that's why PL_ARENA_DEFAULT_ALIGN was
defined as sizeof(double).  Today we have other 64-bit types
such as long long and (on 64-bit platforms) pointers, but as
Steve pointed out in comment 6, 8 is still a good default
alignment.  Do you agree?  If we define PL_ARENA_DEFAULT_ALIGN
simply as 8, would it break any platform?

Comment 10

[Brendan Eich [:brendan]]

Sure, 8 as manifest alignment grain is fine.

/be