386885 - Removal of JSAtom.number

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

Attachment: implementation v1

Currently JSAtom.number is used as a hash source when storing atoms in various hash tables. This is redundant since JSAtom* is stable and can be used for hashing just as well.

The attached patch implements such hashing and removes JSAtom.number. The patch  uses jsid directly as a hash code in jsscope.c so the type bits of the id contributes to the hashing.

The patch also removes flags from various js_AtomizeX methods since all the calls to the methods uses 0 for flags.

Comment 1

[Brendan Eich [:brendan]]

Should this block the big double hashing for atom table bug?

Just for grins and cuz it's there, could you turn on the metering and show good hashtable performance with the new hash function input?

/be

Comment 2

[Brendan Eich [:brendan]]

Comment on attachment 270946 [details] [diff] [review]
implementation v1

See last comment. Patch looks fine apart from this nit:

>+JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4);
>+JS_STATIC_ASSERT(sizeof(JSAtom *) == JS_BYTES_PER_WORD);

One blank line here to space the JS_STATIC_ASSERT group from the #if block would be nice.

>+#if JS_BYTES_PER_WORD == 4

/be

Comment 3

[Igor Bukanov]

This bug indeed blocks 386265 and t o check the hashing performance I need bug 387229.

Comment 4

[Igor Bukanov]

With a prototype of the patch from bug 387229 comment 0 applied I got for hashing performance for simple browser startup/shutdown:

Before the removal of JSAtom.number:

Scope stats:
  searches:       444781
  hits:           290936 65.41%
  misses:          88311 19.85%
  hashSearches:   254331 57.18%
  steps:           97291 21.87% 38.25% <-- number to watch, steps/hashSearches
  stepHits:        42735  9.61% 16.80%
  stepMisses:      22799  5.13%  8.96%
  adds:            28865
  redundantAdds:     527
  addFailures:         0
  changeFailures:      0
  compresses:          0
  grows:             535
  removes:            29
  removeFrees:        28
  uselessRemoves:      0
  shrinks:             0

After the removal and using id as a hash:

Scope stats:
  searches:       444760
  hits:           313029 70.38%
  misses:          85995 19.34%
  hashSearches:   254328 57.18%
  steps:           87039 19.57% 34.22%  <-- number decreases
  stepHits:        20636  4.64%  8.11%
  stepMisses:      25100  5.64%  9.87%
  adds:            28865
  redundantAdds:     527
  addFailures:         0
  changeFailures:      0
  compresses:          0
  grows:             535
  removes:            29
  removeFrees:        29
  uselessRemoves:      0
  shrinks:             0

This means that for this particular case using id as hash is more efficient than JSAtom->number. I think the fact that malloc address is more random than atom's allocation number contributes to that.

Comment 5

[Igor Bukanov]

Comment on attachment 270946 [details] [diff] [review]
implementation v1

A new patch is comming. It is possible to remove JSAtom.flags as well and use JSAtom.entry.value both for flags and hidden atom link.

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #5)
> (From update of attachment 270946 [details] [diff] [review])
> A new patch is comming. It is possible to remove JSAtom.flags as well and use
> JSAtom.entry.value both for flags and hidden atom link.

Could do, or better in my book to cut to the chase (bug 386265) and not go through more intermediate states.

/be

Comment 7

[Igor Bukanov]

(In reply to comment #6)
> Could do, or better in my book to cut to the chase (bug 386265) and not go
> through more intermediate states.

You are right, it is indeed a waste of efforts as any optimizations of hidden atom storage will be removed by a patch for bug 386265. This is very different from removal of JSAtom.number. It is pretty much a requirement for bug 386265 as it performs the necessary id hashing refactoring.

So I will just sync v1 with the trunk and address the nits.

Comment 8

[Igor Bukanov]

Attachment: implementation v2

The new version that, besides syncing with trunk to reflect changes from bug   	385729 and addressing the nits from comment 2, adds jsop_int8 and jsop_int32 bytecodes to avoid atomization of negative numbers and an entry in JSScript.atomMap. It allowed to remove js_AtomizeBool and js_AtomizeInt calls. 

The patch also uses jsval for int and bool directly as atom hash so true and 0 would not have  the same hash. Although in the view of bug 386265 this is a useless optimization, but it also removes some macros and functions that an implementation for that bug would also remove. Thus it counts towards that bug.

Comment 9

[Igor Bukanov]

(In reply to comment #8)
> Created an attachment (id=271431) [details]
> implementation v2

The patch has to bump xdr version as the decompiler no longer supports JSOP_DOUBLE (former JSOP_NUMBER) when JSVAL_IS_INT(ATOM_KEY). The new int8 and int32 bytecodes removed the need for that.

Comment 10

[Brendan Eich [:brendan]]

That wasn't a patch, it was stderr:

ssh: cvs.mozilla.org: Temporary failure in name resolution
cvs [diff aborted]: end of file from server (consult above messages if any)

I'm glad to see revisiting of 11- and indeed 12-year-old design decisions about constant bytecoding and memoization. Penalizing negative numbers seemed ok back in 1995 (the original Mocha runtime, whose atom table was adapted without much change into the "js/ref" runtime that's known as SpiderMonkey in fall 1996).

Looking forward to the new patch ;-).

/be

Comment 11

[Igor Bukanov]

Attachment: implementation v2 for real

Here is the proper patch.

Comment 12

[Igor Bukanov]

Attachment: implementation v3

The new version stores jsval directly in JSCodeGenerator.constList instead of wrapping it into jsid. The latter is wrong as id can not wrap atoms with jsdouble as a key.

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 271466 [details] [diff] [review]
implementation v3


>+    JS_ASSERT(JSVAL_IS_INT(v) | (v == JSVAL_TRUE) | (v == JSVAL_FALSE) |
>+              (v == JSVAL_NULL) | (v == JSVAL_VOID));

Why the | (which forces overparenthesization)? || seems best (short-circuiting).

>             /* Finally, add an entry for atom into the hash bucket at hep. */
>-            ale = (JSAtomListElement *)
>-                  JS_HashTableRawAdd(al->table, hep, atom->number, atom, NULL);
>+            ale = (JSAtomListElement *)JS_HashTableRawAdd(
>+                      al->table, hep, ATOM_HASH(atom), atom, NULL);

Nit: break after cast, then break as needed after actual args, underhanging first actual.

>+# define ATOM_HASH(atom)          ((JSHashNumber)((jsuword)(atom) >> 3) ^     \
>+                                   (JSHashNumber)((jsuword)(atom) >> 35))

Could use IS_{BIG,LITTLE}_ENDIAN and use more bits -- or am I misunderstanding the reason for the >> 35?


> /*
>  * This variant handles all primitive values.
>  */
> extern JSAtom *
>-js_AtomizePrimitiveValue(JSContext *cx, jsval value, uintN flags);
>+js_AtomizePrimitiveValue(JSContext *cx, jsval value);

Pre-existing nit: v, not value, for the formal parameter name.

> 
> /*
>  * Convert v to an atomized string.
>  */
> extern JSAtom *
> js_ValueToStringAtom(JSContext *cx, jsval v);

[snip...]

>+            /*
>+             * We atomize double to root jsdouble instance that we wrap as

"a jsdouble instance"

>+             * jsval and store in cg->constList as atoms are blocked from GC
>+             * during compilation.

Comma before "as", and s/blocked/protected/

>+#define GET_INT8(pc)            ((jsint)(int8)((pc)[1]))

Overparenthesized (pc)[1].

>+
>+#define GET_INT32(pc)           ((jsint)(((uint32)((pc)[1]) << 24) |          \
>+                                         ((uint32)((pc)[2]) << 16) |          \
>+                                         ((uint32)((pc)[3]) << 8)  |          \
>+                                         (uint32)((pc)[4])))

Ditto.

Hey, maybe I should use that UNUSED117 opcode in the patch for bug 385393, and then you can make the two new JSOP_INT* ops adjacent?

/be

Comment 14

[Igor Bukanov]

Attachment: implementation v4

Here is a version to address the nits. It defines ATOM_HASH as:

#if JS_BYTES_PER_WORD == 4
# define ATOM_HASH(atom)          ((JSHashNumber)(atom) >> 2)
#elif JS_BYTES_PER_WORD == 8
# define ATOM_HASH(atom)          (((JSHashNumber)(atom) >> 3) ^              \
                                   (JSHashNumber)((jsuword)(atom) >> 32))
#else
# error "Unsupported configuration"
#endif

Since one can not assume anything about upper bits of a pointer on 64-bit platforms, xoring two parts of the word should be a reasonable hashing strategy.

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 271533 [details] [diff] [review]
implementation v4

>+            /*
>+             * We atomize double to root a jsdouble instance that we wrap as
>+             * jsval and store in cg->constList. It works since atoms are

Final nit: "This works because atoms are" is better.

r=me with that.

/be

Comment 16

[Igor Bukanov]

Attachment: implementation v4b

Here is aversion with the last nit addressed.

Comment 17

[Igor Bukanov]

I committed the patch from comment 16 to the trunk:

Checking in js.c;
/cvsroot/mozilla/js/src/js.c,v  <--  js.c
new revision: 3.156; previous revision: 3.155
done
Checking in jsatom.c;
/cvsroot/mozilla/js/src/jsatom.c,v  <--  jsatom.c
new revision: 3.100; previous revision: 3.99
done
Checking in jsatom.h;
/cvsroot/mozilla/js/src/jsatom.h,v  <--  jsatom.h
new revision: 3.71; previous revision: 3.70
done
Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.265; previous revision: 3.264
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.359; previous revision: 3.358
done
Checking in jsopcode.c;
/cvsroot/mozilla/js/src/jsopcode.c,v  <--  jsopcode.c
new revision: 3.255; previous revision: 3.254
done
Checking in jsopcode.h;
/cvsroot/mozilla/js/src/jsopcode.h,v  <--  jsopcode.h
new revision: 3.50; previous revision: 3.49
done
Checking in jsopcode.tbl;
/cvsroot/mozilla/js/src/jsopcode.tbl,v  <--  jsopcode.tbl
new revision: 3.99; previous revision: 3.98
done
Checking in jsparse.c;
/cvsroot/mozilla/js/src/jsparse.c,v  <--  jsparse.c
new revision: 3.293; previous revision: 3.292
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.66; previous revision: 3.65
done
Checking in jsscope.h;
/cvsroot/mozilla/js/src/jsscope.h,v  <--  jsscope.h
new revision: 3.47; previous revision: 3.46
done
Checking in jsxdrapi.c;
/cvsroot/mozilla/js/src/jsxdrapi.c,v  <--  jsxdrapi.c
new revision: 1.34; previous revision: 1.33
done
Checking in jsxdrapi.h;
/cvsroot/mozilla/js/src/jsxdrapi.h,v  <--  jsxdrapi.h
new revision: 1.32; previous revision: 1.31
done

Comment 18

[Igor Bukanov]

To anybody who notice troubles with http://tinderbox.mozilla.org/Firefox/: I have to leave until 14:00 UTC so if the tinderbox would show problems just take out the patch from comment 16.