5 ms·

Mozilla’s new (internal) JavaScript value representation

69 points by mbrubeck 16y ago

jws 16y ago
Clever, but slightly scary. They tag their object/string/integer/floats by storing them all in 64 bits, top 32 bits is tag, noting that there are vast swathes of values in the IEEE float format that are all NaN and the hardware and libraries only use one. But woe to the poor beggar that uses the wrong NaN. And fear the nasty man that slips the wrong NaN in through a tricky mechanism and turns it to a pointer. (For similar problems, I was always fond of the mechanism in the Mindy Dylan interpreter. There all pointers had their low bit set, and integers had a low bit of zero. The nifty part being that integer math still worked without shifting and for pointers you are generally indexing to an offset anyway so take the one off there and it is free. Mercifully I've forgotten why I had to read enough of their source code to discover that.)
- jganetsk 16y ago
  You have to shift on multiplication and division.
- malkia 16y ago
  Another way is to use bibop memory organization (Big Bag Of Pages). http://www.google.com/search?q=bibop+memory+organization+(Big+Bag+Of+Pages) http://www.google.com/search?q=bibop+memory+organization+(Bi...
  - dfox 16y ago
    But BiBOP (aside from being hard to implement on modern platforms) does not get you direct fixnums (or flonums in this case).
- andhow 16y ago
  The VM controls the creation and manipulation of doubles, so beggars and nasties do not have the ability to create a non-canonical NaN.
  - jws 16y ago
    There is a foreign function interface floating around in Mozilla land. js-ctypes. I have no idea how it relates to this javascript engine, but it tantalizes.
    - andhow 16y ago
      js-ctypes goes through the JSAPI, so the JS engine can still guard against rogue NaNs.
- nostrademons 16y ago
  This representation reminded me a lot of the one used in Gwydion Dylan. That also used a two-word representation - mostly, if the compiler could statically infer the type it'd leave off the tag - with one word for the type tag and one word for the value. IIRC, they ran into some very serious problems with threading. If you use a two-word representation, you can't atomically set a value - there's always the chance that the thread will be pre-empted in between setting the value and the tag and some other thread will be able to run. This of course is disaster, because you'll get a value interpreted as a type that it's not. I wonder how Mozilla plans to handle this. Is their JS engine inherently single-threaded only? Fine-grained locking seems impractical, because you'd need locks around every assignment. Would they do something like Python's GIL? What's the reason behind this representation anyway? It was an interesting experiment when Gwydion did it, but I don't really see the practical benefit.
  - pmjordan 16y ago
    If you use a two-word representation, you can't atomically set a value. At least on 32-bit x86 this isn't true. CMPXCHG8B can atomically write 64 bits of data and has been supported by CPUs for decades. The x86-64 equivalent, CMPXCHG16B, for atomic 128-bit writes is more problematic, as early Athlon64/Opteron CPUs did not support it. But even on 64-bit systems, a 64-bit encoding should be good enough. Technically, the address space can comprise 48 bits, but even if you steal a couple more than 16 for the NaN coding you should have more than enough for a few decades. PowerPC, ARM, etc. have different atomicity guarantees though, which make this sort of thing more problematic. However, as far as I know, even Web Worker threads don't share JS context state with the main thread, so this is probably a non-issue. I don't really see the practical benefit. Probably to avoid cache misses.
  - pcwalton 16y ago
    JavaScript will never support threads in the usual sense, as long as /be has his say: http://weblogs.mozillazine.org/roadmap/archives/2007/02/threads_suck.html http://weblogs.mozillazine.org/roadmap/archives/2007/02/thre... So JS won't need fine-grained locking in the foreseeable future.
    - 16y ago
malkia 16y ago
The double float tagging using NaN sounds like LuaJIT's approach quoting http://article.gmane.org/gmane.comp.lang.lua.general/58908 http://article.gmane.org/gmane.comp.lang.lua.general/58908 - NaN-tagging: 64 bit tagged values are used for stack slots and table slots. Unboxed floating-point numbers (doubles) are overlayed with tagged object references. The latter can be distinguished from numbers via the use of special NaNs as tags. It's a remote descendant of pointer-tagging. [The idea dates back to 2006, but I haven't disclosed it before 2008. Special NaNs have been used to overlay pointers before. Others have used it for tagging later on. The specific layout is of my own devising.]
- andhow 16y ago
  It is also used in WebKit's JSC. Using the NaN space goes back much further than LuaJIT. E.g., you can see it mention in this 1993 survey paper: http://lambda-the-ultimate.org/node/3912 http://lambda-the-ultimate.org/node/3912.
  - malkia 16y ago
    Thanks for the paper! Quite interesting and easy read.
- deleted 16y ago
  [deleted]
tedunangst 16y ago
Is it just me, or does the first example assign to 4 variables, not 3?
yason 16y ago
How is this new but merely evolutional? You know, as soon as you're willing pass 64-bit values around, packing different values into a long long isn't really packing anymore. There are so many bits that you can easily "waste" a few of them for tags. The downside is that you most often really just need only a handful of bits and it looks like Jaegermonkey lavishly uses 32 bits for tagging of 32-bit pointers. Of course, thinking optimistically, the new approach is better if you can at least carry some satellite information in the 32 tag bits, like object origination/permission/context data, or some length/offsets for (sub)strings. Also, locality is probably better, heap allocation is eliminated, and for 64-bit registers and moves this is a natural fit. But I would have liked to see those 61-bit integers for the same amount of money.
- andhow 16y ago
  Of course this is not new. I would have to assume that every value representation under the sun has already been invented and probably during the 60s. 61-bit integers would either require long long integer arithmetic on x86 or require more dynamic branching for arithmetic ops either of which would slow down very hot paths.

69 points by mbrubeck 16y ago

jws 16y ago

Clever, but slightly scary. They tag their object/string/integer/floats by storing them all in 64 bits, top 32 bits is tag, noting that there are vast swathes of values in the IEEE float format that are all NaN and the hardware and libraries only use one. But woe to the poor beggar that uses the wrong NaN. And fear the nasty man that slips the wrong NaN in through a tricky mechanism and turns it to a pointer. (For similar problems, I was always fond of the mechanism in the Mindy Dylan interpreter. There all pointers had their low bit set, and integers had a low bit of zero. The nifty part being that integer math still worked without shifting and for pointers you are generally indexing to an offset anyway so take the one off there and it is free. Mercifully I've forgotten why I had to read enough of their source code to discover that.)

jganetsk 16y ago
You have to shift on multiplication and division.
malkia 16y ago
Another way is to use bibop memory organization (Big Bag Of Pages). http://www.google.com/search?q=bibop+memory+organization+(Big+Bag+Of+Pages) http://www.google.com/search?q=bibop+memory+organization+(Bi...
- dfox 16y ago
  But BiBOP (aside from being hard to implement on modern platforms) does not get you direct fixnums (or flonums in this case).
andhow 16y ago
The VM controls the creation and manipulation of doubles, so beggars and nasties do not have the ability to create a non-canonical NaN.
- jws 16y ago
  There is a foreign function interface floating around in Mozilla land. js-ctypes. I have no idea how it relates to this javascript engine, but it tantalizes.
  - andhow 16y ago
    js-ctypes goes through the JSAPI, so the JS engine can still guard against rogue NaNs.
nostrademons 16y ago
This representation reminded me a lot of the one used in Gwydion Dylan. That also used a two-word representation - mostly, if the compiler could statically infer the type it'd leave off the tag - with one word for the type tag and one word for the value. IIRC, they ran into some very serious problems with threading. If you use a two-word representation, you can't atomically set a value - there's always the chance that the thread will be pre-empted in between setting the value and the tag and some other thread will be able to run. This of course is disaster, because you'll get a value interpreted as a type that it's not. I wonder how Mozilla plans to handle this. Is their JS engine inherently single-threaded only? Fine-grained locking seems impractical, because you'd need locks around every assignment. Would they do something like Python's GIL? What's the reason behind this representation anyway? It was an interesting experiment when Gwydion did it, but I don't really see the practical benefit.
- pmjordan 16y ago
  If you use a two-word representation, you can't atomically set a value. At least on 32-bit x86 this isn't true. CMPXCHG8B can atomically write 64 bits of data and has been supported by CPUs for decades. The x86-64 equivalent, CMPXCHG16B, for atomic 128-bit writes is more problematic, as early Athlon64/Opteron CPUs did not support it. But even on 64-bit systems, a 64-bit encoding should be good enough. Technically, the address space can comprise 48 bits, but even if you steal a couple more than 16 for the NaN coding you should have more than enough for a few decades. PowerPC, ARM, etc. have different atomicity guarantees though, which make this sort of thing more problematic. However, as far as I know, even Web Worker threads don't share JS context state with the main thread, so this is probably a non-issue. I don't really see the practical benefit. Probably to avoid cache misses.
- pcwalton 16y ago
  JavaScript will never support threads in the usual sense, as long as /be has his say: http://weblogs.mozillazine.org/roadmap/archives/2007/02/threads_suck.html http://weblogs.mozillazine.org/roadmap/archives/2007/02/thre... So JS won't need fine-grained locking in the foreseeable future.
  - 16y ago

malkia 16y ago

The double float tagging using NaN sounds like LuaJIT's approach quoting http://article.gmane.org/gmane.comp.lang.lua.general/58908 http://article.gmane.org/gmane.comp.lang.lua.general/58908 - NaN-tagging: 64 bit tagged values are used for stack slots and table slots. Unboxed floating-point numbers (doubles) are overlayed with tagged object references. The latter can be distinguished from numbers via the use of special NaNs as tags. It's a remote descendant of pointer-tagging. [The idea dates back to 2006, but I haven't disclosed it before 2008. Special NaNs have been used to overlay pointers before. Others have used it for tagging later on. The specific layout is of my own devising.]

andhow 16y ago
It is also used in WebKit's JSC. Using the NaN space goes back much further than LuaJIT. E.g., you can see it mention in this 1993 survey paper: http://lambda-the-ultimate.org/node/3912 http://lambda-the-ultimate.org/node/3912.
- malkia 16y ago
  Thanks for the paper! Quite interesting and easy read.
deleted 16y ago
[deleted]

tedunangst 16y ago

Is it just me, or does the first example assign to 4 variables, not 3?

yason 16y ago

How is this new but merely evolutional? You know, as soon as you're willing pass 64-bit values around, packing different values into a long long isn't really packing anymore. There are so many bits that you can easily "waste" a few of them for tags. The downside is that you most often really just need only a handful of bits and it looks like Jaegermonkey lavishly uses 32 bits for tagging of 32-bit pointers. Of course, thinking optimistically, the new approach is better if you can at least carry some satellite information in the 32 tag bits, like object origination/permission/context data, or some length/offsets for (sub)strings. Also, locality is probably better, heap allocation is eliminated, and for 64-bit registers and moves this is a natural fit. But I would have liked to see those 61-bit integers for the same amount of money.

andhow 16y ago
Of course this is not new. I would have to assume that every value representation under the sun has already been invented and probably during the 60s. 61-bit integers would either require long long integer arithmetic on x86 or require more dynamic branching for arithmetic ops either of which would slow down very hot paths.