![[feed]](/wp-content/feed-icon-14x14.png){kind=icon}
18 May 2011 4:57 PM (javascript | ecmascript | scheme | igalia | guile)
In my last note I mentioned that I had been doing a lot of reading of JavaScript implementation code. One point that I didn't mention is that the state of the art is completely undocumented. So to work on rectifying that, here's the first in what might be a series of articles about the internals of JavaScript implementations.
tagging
Initially, all JavaScript implementations used tagged pointers to represent JS values. This is a old trick that comes from the observation that allocated memory takes up at least 4 or 8 bytes, and are aligned in such a way that the least significant bit or three will be zero.
Here's an old part of the Guile manual that explains the technique. For example you could take values whose lowest bit is 1 to be a pointer to the heap. Any value that ends in 0 could be an integer, represented directly in the bits of the pointer. (If your pointer tag is not 0, you will have to mask off the low bits before dereferencing a pointer..)
Google's V8 JavaScript engine still does it this way. This yields 31-bit immediate signed integers; you can just do a signed right-shift to get the value. They call them "smi" values, for "small integers"; they are more commonly called "fixnums". There are other fun tricks you can do to avoid shifts for some common operations, like addition. Note that they also take advantage of the four-byte alignment (in their case) to encode another immediate value, "failure objects", using the other low bit.
The size of a tagged pointer is the size of a pointer, so 32 bits on a 32-bit machine, and 64 on a 64-bit machine. V8 doesn't actually use 63-bit smi values on 64-bit machines, AFAIK.
nan-boxing
JavaScriptCore, the implementation used by WebKit, switched from tagged pointers to a "nan-boxed" format. The best explanation of this strategy is given by Rob Sayre of Mozilla. I believe the technique was first made popular by LuaJIT, though I would appreciate additional references.
Sayre does a good job of explaining things, but to recap, there are about 253 bit patterns that represent not-a-number values for IEEE-754 double-precision floats, but that only one of those is actually emitted by current hardware and software. So cheeky implementations are free to use the other patterns for their own purposes.
What I always wondered when I heard about this strategy was how 53 bits were possibly enough, for a 64-bit machine. How are you going to fit a pointer in that space?
Well it turns out that on x64-64 systems, you only have a 48-bit address space, currently anyway. The shape of that space is quite peculiar, too. I don't know whether Linux gives out addresses in the upper half, but Windows does not, though Solaris does.
Anyway, the other way of looking at NaN-boxing is that there are 264 - 248 values in a pointer that aren't being used, and we might as well stuff something in them, and hey, the whole space of valid double precision numbers fits!
It's convenient too that numbers in JS are specified as doubles. (Even still, all implementations define separate "small integer" types, for use in loops and indexing and such; integer operations are faster when you can use them, too.)
JSC's implementation of nan-boxing is described here, and you can see some of the neat tricks they do here. It actually makes me envious of C++, as a C programmer!
nun-boxing
So, when you choose to do nan-boxing, you basically choose to do one of two things: you favor pointers, or you favor doubles. To favor pointers means that you recognize pointers as having initial (most-significant) 0 bits; if the initial bits are not 0, then it's a double, and you have to add or subtract a bit pattern to get to the double value.
Favoring doubles means that pointers are left as NaN values, so their initial bits are all ones (or the sign bit can be unset, it doesn't matter), and to unpack a pointer, you have to rotate the double space around.
Amusingly, there is a third option as well. For 32-bit machines, you can address the second word in the double directly, so there is no need to mask off anything. This is the JSVALUE32_64 case mentioned in the JSValue code I linked to above.
JSC chose to favor pointers, and as the first JS implementation to nan-box, got to call their choice "nan-boxing". Mozilla chose to favor doubles, and so made up the silly name "nun-boxing".
get thee to a nun boxery?
So you're implementing a language. Should you nan-box or not? I can't say in your case but I can give a couple of examples.
NaN-boxing has the obvious advantage of not allocating doubles on the heap. This reduces cache pressure, GC pressure, and such. That's why Moz and JSC chose it.
V8 on the other hand has not chosen it, at least not yet, anyway. I think that one reason is because especially on embedded devices, and to an extent on ia32, passing around 64-bit values is a big lose. It's so bad that I understand that Mozilla actually passes these values by reference instead of by value in some places, on 32-bit systems only.
But the real reason that V8 doesn't nan-box I think is that they have a compiler that is able to unbox values in registers and in temporary stack locations, both as int32 values and as double values. This works for loops and such things in a function, and is obviously quite efficient, as you don't need to box and unbox at all. Passing doubles as arguments or return values however does allocate them on the heap, as far as I can tell anyway.
Also there is the hackery that with NaN-boxing, you assume things about your OS's memory management. A language implementation should be able to get around this with use of mmap at specific addresses, but still, it's tricky.
I looked at doing nan-boxing for Guile, and eventually decided against it. Guile has a few more constraints that V8 does not have. Firstly it is very portable, so it can't rely the address range constraints that x86-64 has, not without some hackery. It's also portable to the low end, like V8, so 64-bit values are a lose there.
But the killer is the conservative GC on 32-bit systems. If you represent integers with the tag in the high bits, as you would with nan-boxing, then the lower 32 bits are not distinguishable from a pointer, so they can cause the GC to retain heap objects for longer than it should. With tagged pointers, the low-bit masking lets the GC know that an integer is not a pointer. If you were to reintroduce low-bit tagging to a nan-boxed system, you've lost much of the advantage of it. Furthermore if you want to support more than 32 bits of precision in a fixnum, then on a 32-bit system you need to play games with sign extension of a 48-bit value to a 64-bit value, and for all word sizes it looks like the overhead will be significantly higher than tagging.
Finally I think that if we're really going to shoot for the moon, we should implement something like V8's Crankshaft compiler that does decent type inference, to allow unboxed values in registers and on the stack. (For readers of source code, "crankshaft" is basically the "hydrogen" flow-graph code plus a "lithium" assembler. Confusing, right?)
Well that's all for now. If you corrections, or an idea for a further topic, let me know in the comments. Thanks!
18 May 2011 9:48 PM
I have discussed this topic with someone who is working on a nun-boxing implementation of R5RS Scheme. He is restricting the non-doubles to be *signaling* NaNs, thus avoiding the unsafe assumption that only one particular (quiet) NaN is *the* representation of NaN.
Chibi Scheme, which uses the tagged pointer system, used to have a configuration-time option (for 64-bit systems only) to use 32-bit floats as Scheme inexact values, directly embedded in the pointer. Apparently this has been removed now.
19 May 2011 7:14 AM
v8 won't have 63-bit small integers because JavaScript doesn't have an integer type at all. Every number in play is just an IEEE-754 double precision number, which of course can't represent all 64-bit integer values (integers of magnitude up to 2**53ish, yes, but past that some integer values just don't exist). So there's no real reason to have larger small integers, and indeed there might be some reason not to, because adding 32-bit numbers may well be slightly faster than adding 64-bit numbers.
The most ideal non-31-bit integer value to have would probably be 32-bit integers -- crypto algorithms in particular could benefit from not having to go to double when the high bit gets set, although runtime techniques can substantially mitigate this cost -- but again I suspect the 32-bit add versus 64-bit add is problematic.
6 June 2011 1:47 PM
Here's an article pointing to a 1993 paper on value representation techniques (nice, easy read) which also mentions NaN tagging briefly:
http://lambda-the-ultimate.org/node/3912
10 June 2011 6:52 PM
Good summary of the main design points and tradeoffs. Some comments:
On nax-boxing or not, my guess is that the original reason V8 didn't nan-box is that they have always had a good generational GC, which makes allocating doubles on the stack pretty cheap. In systems that don't have generational GC, putting doubles on the heap was way too expensive. And even with V8's generational GC, before Crankshaft came out, Jaegermonkey and Tracemonkey were generally faster on floating-point code, because of the nan-boxing.
Once you have an optimizing compiler that can operate mostly on unboxed values (Tracemonkey and Crankshaft), then the boxing format doesn't matter much at all, because you are not using boxed values in hot code. But I really doubt Crankshaft influenced the value format of the original V8.
I'm a bit surprised about your point about conservative GC--is an untagged int that likely to point inside the GC heap? We currently use conservative GC but we haven't had any evidence that that problem bites us, and I'm sure there's a lot more random stuff than boxed values on the C stack anyway, at least in a browser.
To add further to what Jeff says, floating point arithmetic seems to be about as fast as integer arithmetic now, so the big cost of using floats is in conversion to ints, which happens for bitops and array indices. But bitop inputs are always logically 32 bits in JS and array indices are going to be 32 bits or less in practice.
26 November 2011 0:13 AM
"If your pointer tag is not 0, you will have to mask off the low bits before dereferencing a pointer."
Don't most processors these days have a mem[ptr-const] addressing mode?
23 December 2011 6:59 PM
Nice article! Just a few nits: the name "nunbox" refers to nan-boxing on 32-bit architectures and is roughly equivalent to JSC's JSVALUE32_64 (the 'u' in 'nunbox' is for 'unboxed' since, as you pointed out, the low word is unboxed). The 64-bit nan-boxing encoding used by SpiderMonkey is named "punboxing" (the 'p' is for 'packed', since this scheme is logically like nunboxing, but with all the unused bits sucked out).
18 March 2013 3:38 PM
The IEEE 754 tagged pointer representation used by LuaJIT was first invented in 1997 for an implementation of parallel Haskell.
12 May 2014 2:32 PM
Sandro: NaN-boxing is older than the parallel Haskell technique -- it was for example described by Gudeman in section "2.6.1 Using IEEE NaN Codes" of "Representing Type Information in Dynamically Typed Languages" (1993).
21 July 2015 1:05 AM
> I don't know whether Linux gives out addresses in the upper half, but Windows does not, though Solaris does.
Linux seems to only use the upper half for virtual syscalls on my current kernel build:
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
It's probably a build-time option, though.
30 March 2017 12:34 PM
It's actual for now? I about webKit.
3 April 2017 6:56 AM
you website is quite heplful. For more check https:irenovate.in
6 April 2017 12:47 PM
thnak you! It's actual for now?
6 April 2017 12:54 PM
[URL]http://wallpaperis.com[/URL] thank you!
9 April 2017 10:13 AM
It is good information. Actually, javascript is a good browser script language but you need to implement properly to work.
24 April 2017 10:14 AM
Using FastPokeMap we have easily to found the Pokemon nearby your location. Pokemon Tracker Apk is an app which provides tracking service for discovering the location of any Pokemon that’s been found by other players in your Area.FastPokeMap
28 April 2017 6:32 AM
http://www.eubusiness.com/author/techiestate
https://musicbrainz.org/user/techiestate
http://www.washblog.com/user/techiestate
https://www.kickstarter.com/profile/1347464078/about
http://glitter-graphics.com/users/techiestate
http://www.buzzsprout.com/97468
11 May 2017 10:09 AM
I feel that will affirm your suspicions. So here I go bordering on Virility EX because you have to weigh the conditions. This means double trouble. This was a tempting offer. I told them what they want to do. This installment may seem a bit haphazard at first to you. That is a transparent checklist which will help you keep on top of stuff. Think about it, "Life is like a box of chocolates, you never know what you are going to get." It was somewhat annoying since it was the first time that I had done this. Read More: http://www.suxorfree.com/virility-ex/
17 May 2017 9:36 AM
I told them what they want to do. This installment may seem a bit haphazard at first to you. That is a transparent checklist which will help you keep on top of stuff. Think about it, kinguserapp.com
30 May 2017 11:02 AM
I don't do it for free. By contrast, there are several Biogenex Testo available. I have by the time mentioned Biogenex Testo ready for me. That is a fast growing market. http://supplementsbook.org/biogenex-testo/
4 June 2017 4:37 AM
The rectus abdominal muscle starts off evolved within the pelvis and extends at some stage in the abdomen. The outside indirect muscle is located at the top and facet surfaces of the abdomen and a part of the chest, and the longest of the abdomen muscular tissues.
For more === >>>>> http://www.healthbeautyfacts.com/elevate-igf-testosterone-booster/
5 June 2017 10:19 AM
Marine Muscle offer a range of premium hardcore alternatives to popular anabolic steroids.
http://www.crazybulkguide.com/marine-muscle/
7 June 2017 6:17 AM
http://moneyinthebanklive.com/category/wwe/
11 June 2017 7:42 PM
Vital Nutra Both manner, this leads them to the concept of using male enhancement products. However, how safe is male enhancement? How credible are the claims in their manufacturers and manufacturers.For More === >>>>> http://www.healthbeautyfacts.com/vital-nutra/
14 June 2017 1:21 AM
Both manner, this leads them to the concept of using male enhancement products
http://indvspaklivehighlights.com/ver-money-inthe-bank-2017-en-vivo-fox-sports/
indvspaklivehighlights.com/wwe-mitb-2017-live-streaming-free/
14 June 2017 1:23 AM
http://indvspaklivehighlights.com/hotstar-live-cricket-icc-ct-2017/
http://indvspaklivehighlights.com/cricket-match-online-live-streaming/
http://indvspaklivehighlights.com/willow-tv-cricket-live-streaming/
14 June 2017 1:25 AM
http://www.goldcup2017live.us/gold-cup-2017-live-usa-vs-martinique/
http://www.goldcup2017live.us/gold-cup-2017-live-usa-vs-panama/
http://www.goldcup2017live.us/gold-cup-2017-live-canada-vs-costa-rica/
21 June 2017 10:50 AM
There is so much wisdom on Perfect Figure available. Have you ever wished for a Weight Loss? It is what newbies need. This column will point out my personal secrets for dealing with this solution. I won't be using it.
Visit here: http://www.garciniasstore.com/trim-biofit-garcinia/
21 June 2017 10:48 PM
So you're implementing a language. Should you nan-box or not? I can't say in your case but I can give a couple of examples.
22 June 2017 3:42 AM
So you're implementing a language. Should you nan-box or not? I can't say in your case but I can give a couple of examples.
27 June 2017 10:34 AM
Java is a very vast language. Thanks for this informative post. Inheritance is a very good topic.
28 June 2017 12:10 PM
It is an acclaimed collection. It means that you will have a greater flexibility with your Weight Loss. Maybe you only feel as if you don't have time for Lose Weigth. I was forgot the biggest change to ever happen to the Lose Weigth business.
Visit here: http://www.slimnojymfacts.com/Phenq/
29 June 2017 6:07 AM
They lived in extravagant style. Do you know how to fix a broken Weight Loss? I read the most recent news release. Come on, meet us halfway. Definitely, the problem is solved. That doesn't refute PhenQ Weight loss Pills.
http://http://www.slimnojymfacts.com/Phenq/
6 July 2017 9:28 AM
Hacking android games is easy and simple you just need to hack any android games and then obtain unlimited coins, unlimited life and all so get started. So how to do that? Please help me out? Definitely, the problem is solved. That doesn't refute PhenQ Weight loss Pills.
8 July 2017 11:03 AM
Wow!wonderful blog.After reading this blog I get to know more about the basics of hacking and its best and effective uses.
http://emailsupportnumber.org/yahoo-mail-customer-support-number/
8 July 2017 11:03 AM
Wow!wonderful blog.After reading this blog I get to know more about the basics of hacking and its best and effective uses.
11 July 2017 12:30 PM
nice post thanks for sharing
21 July 2017 4:32 PM
The crazybulk bulking stack is a type of nutritional supplement, similar to the other products that are available from crazy bulk. The ingredients that are used in this nutritional supplement are effective and it is the best supplement to provide the muscle weight to the skinny body frame. There are various benefits of using this supplement to gain the weight for a skinny frame. One will be able to achieve the normal body weight, get more nutrition for a healthy body and also get the improved muscle mass. There are also various other supplements from crazy bulk, which when combined with this supplement will definitely provide the best results in a safe manner.
http://musclecontour.com/bulking-stack/
5 August 2017 4:41 PM
The OS provides new alternatives for navigation: Aero Shake, Snap and Jump Lists. These features were developed to smooth out a workflow for the user which makes win 7 home premium 64 bit more efficient and more productive
5 August 2017 4:42 PM
We are continuously trying to make this site a good place that will provide every material that comes to daily need. On this beautiful platform, you’ll find all kind of templates related office
5 August 2017 4:44 PM
It tells the complete history of the bigger in very short. It is considered as comparable to the key document and can be read within the place of the key document
20 August 2017 6:46 PM
Java is a very vast language. Thanks for this informative post. Inheritance is a very good topic.
26 August 2017 10:36 AM
The discontent and frustration that you feel is entirely your own creation.
21 October 2017 3:09 AM
Never much of a java script fan but i a die hard C sharp user
27 October 2017 9:05 AM
I like Java language because that was my second choice in IT. well thanks for great information about Java.
27 October 2017 9:39 AM
all indain tv drama you can watch here totlly free and full episode >>>>>http://dramatvhd.com
5 December 2017 7:35 AM
Hi you have done final solution for me thanks keep working always..
7 December 2017 1:42 PM
Thanks i like it good work
7 December 2017 1:44 PM
Great one! that a great information
10 December 2017 6:39 PM
JavaScript are not coded good sometime so it broke the browser.
26 February 2018 4:50 PM
Such an amazing response, God bless you, keep it up! :)
14 March 2018 4:43 AM
Exactly what I was looking for. Thank you!
16 March 2018 9:57 PM
Hey admin your sharing way is unique. I love all the posts, I really enjoyed, I would like more information about this
10 April 2018 12:24 PM
It is really difficult to find such a fantastic content with some useful information.Thank you, I appreciate it!
10 April 2018 5:34 PM
that is really great to see that you are publishing a great content.
26 April 2018 11:18 AM
A really informative web-site. The way you might have share this details is basically really appreciative. Hope to discover far more on this
topic listed here. Many thanks for posting this facts listed here.
26 April 2018 8:06 PM
I am no longer positive where you are getting your information, however great topic.
I must spend a while learning more or understanding more.
Thanks for fantastic information I used to be searching for this info for my
mission.
27 April 2018 8:44 PM
Thanks for another magnificent post. The place else may anybody get that
type of information in such an ideal method of writing?
I’ve a presentation next week, and I am at the look for such info.
27 April 2018 11:42 PM
Saved as a favorite, I love your website! Thanks for another magnificent post. The place else may anybody get that
type of information in such an ideal method of writing?
I have got a presentation next week, and I am at the look for such info.
1 May 2018 8:48 AM
Exactly that the thing , I'm searching for
5 May 2018 12:31 PM
nice blog
9 May 2018 11:10 AM
Really exciting to see it!
9 May 2018 7:43 PM
very nice thanks for sharing
11 May 2018 5:58 PM
This website was… how do I say it? Relevant!!
Finally, I have found something which helped me. Thank you!
11 May 2018 11:25 PM
Quality articles or reviews is the important to be a focus for the people to go to see the web site, that’s
what this site is providing
15 May 2018 7:19 PM
This design is incredible! You obviously know
how to keep a reader entertained. Between your wit
and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Wonderful job. I really loved what
you had to say, and more than that, how you
presented it. Too cool!
20 May 2018 12:59 PM
Impressive work! truly amazing, I like you work.
21 May 2018 10:52 AM
Well these kind of representations in javascript is very important and i hope you have done a tremendous job in representing them here! :)
23 May 2018 8:06 PM
Quality articles or reviews is important to be a focus for the people to go to see the website, that’s
what this site is providing
23 May 2018 8:07 PM
A really informative web-site. The way you might have share this details is basically really appreciative. Hope to discover far more on this
topic listed here. Many thanks for posting this facts listed here.
23 May 2018 9:03 PM
Thank you for the post loved it
31 May 2018 7:24 PM
A very Good Place To Visit. Good Work I really Impress...Keep it up
7 June 2018 5:52 PM
Wow, this is one of the best article i have seen
7 June 2018 11:58 PM
wow nice blog thanks
9 June 2018 6:37 PM
Well this is one of the website i just came across
12 June 2018 5:35 AM
nice post thanks for admin
2 July 2018 9:03 AM
Keep posting the great stuff. Keep it up gys.
6 July 2018 12:27 PM
Rapid Tone Shark Tank Reviews buying all the food you will would like. If you have hassle with temptations, this time will additionally be used for getting rid of all the unhealthy, fattening, non-diet food out of their house. See more: >>>> http://www.rapidtone-sharktank.com/
27 July 2018 5:37 AM
Luna Trim Diet There is such a huge amount of knowledge in magazines, in outlets and on the internet about the simplest weight loss products most people become utterly bewildered and finish up doing nothing. Or we have a tendency to try every weight loss product on the market without giving each one a honest strive. We have all done it, bought one thing, not seen leads to some days and then determined it didn't work and moved onto the next product.Luna Trim
1 August 2018 3:32 PM
Reading your blog post I browsed your website a little and noticed you aren’t ranking as well in Google as you might be. I possess a handful of blogs myself and I think you should use speed rank seo, just search it on the internet. You’ll find it’s an extremely nice service that's liable to bring you a lot more traffic. Keep up the standard posts!
6 September 2018 8:27 PM
The presentation is extremely well presented.
9 September 2018 7:07 PM
Star Sports is the TV Channel Network which have rights to telecast all sports on TV. Indian Cricket fans enjoy the every feature of Star sports on the cable as well as on sites.
https://cricasiacup2018s.com/2018/09/08/india-vs-pakistan-live-streaming/
https://cricasiacup2018s.com/2018/09/08/hotstar-live-streaming-asia-cup/
9 September 2018 7:08 PM
Pakistan vs India Live Streaming Asia Cup – 19 September 2018 Prediction Match Preview Head to Head Team Squad Highlight The matches of the Asia Cup 2018 is planned to be held in UAE in the period of September 2018.
https://indvspaks.com/2018/09/09/pakistan-vs-india-live-streaming/
https://indvspaks.com/2018/09/09/india-vs-pakistan-live-streaming-hotstar/
11 November 2018 5:41 PM
Well this is one of the website i just came across
3 December 2018 10:33 AM
I like your content. Now look at this.
Movierulz or movie rulz is an online torrent website that publishes leaked movies content on its platform contributing to public domain. This site publishes leaked movies in many languages like English, Hindi, Tami, Telugu, Malayalam etc.
5 December 2018 4:14 PM
Read Harry Potter Quotes below: When we were kids we used to watch a lot of super powers, comical and magical stuff related movies that no doubt still excite us and we just can’t resist ourselves in taking time out for those movies we grew up watching. Harry potter Quotes.
5 December 2018 4:16 PM
Have you ever seen any (best) anime till now. In my childhood, i have seen my friends go crazy about animated movies and they used keep on talking about it every time. After a lot of suggestions by my friends and cousins i gave it a try. And i really liked it. Best anime.
5 December 2018 4:17 PM
For men, there’s nothing more satisfactory thing than riding a bike in the whole world. There comes a time when each one of us feel low at some point of our lives. Do nothing. Take your bike out and go for riding. Riding a bike needs focus and concentration on every controls you have on race, clutch, gears and breaks. Motorcycle quotes.
5 December 2018 4:18 PM
Read Depressing quotes below: What is depression guys? If you have been through depression you should think about this for a while and answer. Basically, depression is nothing but a side effect of something you are afraid of happening in your life or happened in your life because either you can’t do anything about it or the circumstances are like that that are not letting it the way you want it to be and just see it worsening further. Depressing quotes.
5 December 2018 4:20 PM
The Fault in Our Stars was a blockbuster, becoming number one at the box office during its opening weekend, and grossing over $307 million worldwide with a budget of $12 million. It was released on September 16, 2014, and grossed over $42 million in total domestic video sales. The fault in our stars quotes.
5 December 2018 4:21 PM
I don’t drink! I mean sometimes its okay but i am strictly against it but never usually mind if mah friends get over my room with some chilled beer or vodka maybe. Okay! You may be thinking i am drunk. I am not. Alcohol meme.
5 December 2018 4:23 PM
It’s an adage that ‘Motivation should always be INTRINSIC’ ,meaning what comes from your soul, yet people roam around the world which is mostly comprised of the INTERNET these days(i mean as they say it) to find what they lack-A pure source of MOTIVATION which basically inspires them towards the notion of hard work! Inspirational quotes.
10 December 2018 8:28 PM
Cracksfiles if a platform where you can Download full version software with working license, activation Serial key and Activator. Windows 10 Microsoft office Activator download link.
10 December 2018 8:32 PM
Cracksfiles if a platform where you can Download full version software with working license, activation Serial key and Activator. Windows 10 Microsoft office Activator download link.