Closed Bug 386885 Opened 13 years ago Closed 13 years ago

Removal of JSAtom.number

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

Attachments

(1 file, 5 obsolete files)

Attached patch implementation v1 (obsolete) — Splinter Review
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.
Attachment #270946 - Flags: review?(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 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
Attachment #270946 - Flags: review?(brendan) → review+
This bug indeed blocks 386265 and t o check the hashing performance I need bug 387229.

Blocks: 386265
Depends on: 387229
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 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.
Attachment #270946 - Attachment is obsolete: true
(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
(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.
Depends on: 385729
Attached patch implementation v2 (obsolete) — Splinter Review
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.
Attachment #271431 - Flags: review?(brendan)
(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.
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
Attached patch implementation v2 for real (obsolete) — Splinter Review
Here is the proper patch.
Attachment #271431 - Attachment is obsolete: true
Attachment #271458 - Flags: review?(brendan)
Attachment #271431 - Flags: review?(brendan)
Attached patch implementation v3 (obsolete) — Splinter Review
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.
Attachment #271458 - Attachment is obsolete: true
Attachment #271466 - Flags: review?(brendan)
Attachment #271458 - Flags: review?(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
Attached patch implementation v4 (obsolete) — Splinter Review
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.
Attachment #271466 - Attachment is obsolete: true
Attachment #271533 - Flags: review?(brendan)
Attachment #271466 - Flags: review?(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
Attachment #271533 - Flags: review?(brendan) → review+
Here is aversion with the last nit addressed.
Attachment #271533 - Attachment is obsolete: true
Attachment #271732 - Flags: review+
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
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
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.
Flags: in-testsuite-
You need to log in before you can comment on or make changes to this bug.