8 ms·
What is gained and lost with 63-bit integers?
- auvi 12y agoi think the symbolics 3600 had 4 or 8 bit for tags, ocaml is borrowing some more lisp ideas.
- FullyFunctional 12y agoThe ideas behind pointer tagging have been applied and reinvented an astonishingly amount of times, see Knuth and any number of book on the implementation of functional programming languages. To claim symbolics or Lisp invented everything is a bit silly and inaccurate. OT: Thanks to Don Stewart for the two interesting links: https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage... https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Haskell...
- _delirium 12y agoI believe the basic idea dates to the Rice architecture of the late 1950s and 1960s [1]. Although there it wasn't just a programming language implementation technique, but a proposal conceived as a full-on alternative to the Von Neumann architecture [2]. Tagged values as a programming-language implementation technique do seem to take off more towards the early 1970s, though, with the ex-MIT team that would produce the Lisp Machine, and the Xerox team that would produce Smalltalk, both using tagged values prominently. [1] https://en.wikipedia.org/wiki/Rice_Institute_Computer https://en.wikipedia.org/wiki/Rice_Institute_Computer [2] A somewhat later (1973) paper referenced above: http://www.feustel.us/Feustel%20&%20Associates/Advantages.pdf http://www.feustel.us/Feustel%20&%20Associates/Advantages.pd...
- ScottBurson 12y agoMinor correction: the Lisp Machine was created at MIT by MIT staff. Only after it existed did the commercial entities get spun off.
- lispm 12y agoMost Lisp implementations use tag bits. The Symbolics does support it in hardware, though.
- wcummings 12y agoJane Street is a big user of OCaml and have published a sizable amount of code: https://github.com/janestreet https://github.com/janestreet
- boardwaalk 12y agoIn my toy scheme interpreter I used two bits, and so could store integers, pointers to C functions, symbols, bools and characters in an "immediate" form. With the caveat that cells (which contained things that couldn't fit in immediate form) had to be aligned on a four byte boundary. Just showing the different things you can do with tagged pointers I suppose. It's pretty common in Lisp/Scheme runtimes. I love bit twiddling hackery. https://github.com/boardwalk/quuz/blob/master/quuz.h#L13 https://github.com/boardwalk/quuz/blob/master/quuz.h#L13
- infogulch 12y agoWait, with 2 bits you can represent 4 possible values, but you listed 5. What's up with that?
- jbert 12y agoWould you get simpler (faster) ops if you stole the high bit instead of the low bit? e.g. x+y becomes (x + y | (1<<63)) Or does the loss of overflow detection hurt you more?
- breadbox 12y agoSetting the high bit would mean that the integer values are no longer automatically distinguishable from pointer values, which is kind of the whole point.
- TheLoneWolfling 12y agoWhy? You could just check if the high bit is set, instead of if the low bit is set. IIRC, you can do this just by checking if it is less than zero.
- infogulch 12y agoFirst, pointers are typically unsigned integers. Second, memory addresses are virtual, they don't have to exist physically. That is, you don't have to physically have up through 2 quintillion addressable bytes for a pointer with that value to be valid. This is especially true with Address Space Layout Randomization (ASLR) security techniques employed by operating systems. tl;dr: all valid pointer values are possible, regardless of how much memory you actually have.
- TheLoneWolfling 12y agoSo then store the pointer implicitly right-shifted by 1. Means that boxed access is slower, but unboxed access is faster. And, when you get down to the assembly level, it doesn't matter - you can treat an unsigned integer as signed for a comparison if it makes things easier.
- Someone 12y agoThere could be addressable memory with the high bit set, for example ROM space for booting or video memory. That may be rare nowadays (or is it? I remember reading recently that some 64-bit CPU chose to preferably use a memory range from -2GB to +2GB. AMD64?), but whether there is is outside of the control of most language implementers. They can control their own memory allocator, though, and guarantee that it never stores 64-bit quantities at odd addresses.
- aidenn0 12y agoSBCL allows unboxed machine-word sized integers in certain cases. This allows for hand-tuned inner-loops and also efficient coding of algorithms with an implicit MOD 2^64
- jlebar 12y agoThis is similar to "fatvals" in SpiderMonkey (Firefox's JS engine). IIRC SpiderMonkey stores doubles -- the fundamental numeric data type in JS -- as "unboxed" values, using this article's terminology. I'm not sure if there's good documentation about this out there, but it's an interesting hack, and much more complicated than just setting the bottom bit of the value.
- ufo 12y agoI think you are thinking about a different trick called NaN tagging. http://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations http://wingolog.org/archives/2011/05/18/value-representation... The basic idea is that there are 2^53 different bit patterns that are counted as NaN by the computer but only one is actually used in practice. This means that you can "steal" the rest of the NaNs and use them to encode numbers or pointers.
- munificent 12y agoI'm hacking on a fast little dynamically-typed language that uses that technique. It works fantastically well. I describe it in detail here: https://github.com/munificent/wren/blob/master/src/wren_value.h#L400 https://github.com/munificent/wren/blob/master/src/wren_valu...
- ufo 12y agoThanks for the link! I was actually surprised how hard it was to find a good description of NaN tagging yesterday.
- deleted 12y ago[deleted]
- vidarh 12y agoRuby (at least MRI) also uses a similar scheme. This is a fairly common approach with dynamically typed languages.
- phkahler 12y ago>> This is a fairly common approach with dynamically typed languages. That makes sense. The performance penalty might be incremental compared to the overhead of dynamic typing.
- pbsd 12y agoIf LEA is slow, don't use it. A simple ADD followed by DEC outperforms LEA in throughput, latency, and size in recent Intel chips. If you're willing to reduce integers to 62 bits (and assuming no overflows are allowed), multiplication can also be simplified: (2x+1)(2y+1) = 4xy + 2x + 2y + 1. So: t = x + y - 2; // + 1 - 3 p = x * y; // 4*x*y + 2*x + 2*y + 1 return (p - t) >> 1; // (4*x*y + 3) / 2 In amd64, this can be done as ; input in rdi, rsi lea rax, [rdi + rsi - 2] ; slow, but runs concurrently with imul imul rdi, rsi sub rdi, rax shr rdi, 1 ; output
- jzwinck 12y agoGCC generates LEA even for a regular addition, even with -O3 and -march=native on a modern Intel x86-64 system. A simple addition of int64_t gives you: leaq (%rdi,%rsi), %rax Whereas subtracting the tag gives you: leaq -1(%rdi,%rsi), %rax So pretty much the same either way, though you do get five instruction bytes for the tag version vs. four bytes without. Here are the comparisons for multiply and divide, from "gcc -c -O3 -g -march=native" and "objdump -d": x * y: 10: 48 89 f8 mov %rdi,%rax 13: 48 0f af c6 imul %rsi,%rax (x >> 1) * (y - 1) + 1: 40: 48 d1 ff sar %rdi 43: 48 83 ee 01 sub $0x1,%rsi 47: 48 89 f8 mov %rdi,%rax 4a: 48 0f af c6 imul %rsi,%rax 4e: 48 83 c0 01 add $0x1,%rax x / y: 20: 48 89 f8 mov %rdi,%rax 23: 48 99 cqto 25: 48 f7 fe idiv %rsi (((x >> 1) / (y >> 1)) << 1) + 1: 60: 48 89 f8 mov %rdi,%rax 63: 48 d1 fe sar %rsi 66: 48 d1 f8 sar %rax 69: 48 99 cqto 6b: 48 f7 fe idiv %rsi 6e: 48 8d 44 00 01 lea 0x1(%rax,%rax,1),%rax
- pbsd 12y ago3-operand LEA has a different performance profile than 2-operand LEA on Sandy Bridge and later chips. The former has 3 cycle latency and only one execution port, whereas the latter has single-cycle latency and can be dispatched to two execution ports. So while gcc (and every other compiler) may rightly generate an LEA instruction to replace regular addition, it's not optimal when a third argument is added. Curiously, if you need to move the result to another register (say, to respect calling conventions) the optimal solution is a 2-operand LEA plus a DEC: lea rax, [rdi + rsi] dec rax I was wrong about ADD + DEC being smaller, though. I forgot that amd64 took away the 1-byte INC/DEC instructions to serve as REX prefix, so the DEC takes 3 bytes, not 1.
- MichaelGG 12y agoSo this is done to avoid the hassle of having to implement a precise GC?
- orbifold 12y agoNo the garbage collector in Ocaml is just a lot faster than a precise GC could be.
- SeanLuke 12y agoThe Newton had 31-bit integers for the same exact reason. This resulted in the biggest Newton bug in its history: the Year 2010 bug. Like early Macs, the Newton's epoch was January 1, 1904. Times were represented with ints. 1904 + 2^31 seconds = 2010, at which point all sorts of things started failing. https://www.google.com/search?q=Newton+year+2010+bug https://www.google.com/search?q=Newton+year+2010+bug
- glandium 12y agoHow can 1904 + 2^31 seconds = 2010 when 1970 + 2^31 seconds = 2038?
- judk 12y agoParent poster mis-recalled details. The bug is 30-bit signed ints (29bits) with epoch 1993.
- SeanLuke 12y agoGah, indeed I did. The Newton actually has two different epochs, Jan 1 1904 for the OS epoch (same as early Macs) with 32 bits and Jan 1 1993 for the NewtonScript epoch with 29 bits. Someone's tired.
- StefanKarpinski 12y agoCan someone explain why a statically typed Hindley-Milner language like OCaml needs to box everything in the first place?
- kd0amg 12y agoThe garbage collector needs to know what things in memory are pointers/references and what things are actual data.
- StefanKarpinski 12y agoThis seems like a strange tradeoff in that case. Most programs don't have a lot of "loose" integers lying around. Programs that have a lot of integer values tend to store them in arrays, which are themselves tagged and thus have all the information needed to do GC. To save a 64-bit tag per loose integer value (of which there usually aren't very many) this design sacrifices the performance of every integer operation, not to mention memory compatibility with C. I'm curious what kind of code motivated the choice.
- logicchains 12y agoIt's not just loose 'integers'. I believe bools and simple variants are represented as ints, as are empty options.
- StefanKarpinski 12y agoThat's a non-sequitur. Bools require only a single bit and variants/enums don't need all 64 bits. Those are completely distinct cases from the integer case which is fundamental and performance-critical.
- ufo 12y agoThey are exactly the same as integers in that they are not pointers and thus count as dead-ends for the garbage collection algorithm. In theory, you could unbox some extra things at the cost of complicating the garbage collection algorithm and the memory representatio of values. GHC does this for Haskell but the Ocaml guys don't because they highly value keeping the compiler as simple as possible. By the way, integer tagging is only important if your code s heavy in arithmetic operations or floating point operations (Ocaml tries to unbox floating point arrays, but sometimes it has to box floats). This often not that big of a problem and in the worst case you can always link Ocaml with C if you really want to.
- DonHopkins 12y agoThe SPARC has tagged arithmetic (TADDCC), to support Lucid Common Lisp and Smalltalk. http://compilers.iecc.com/comparch/article/91-04-082 http://compilers.iecc.com/comparch/article/91-04-082 http://en.wikibooks.org/wiki/SPARC_Assembly/Arithmetic_Instructions#Tagged_Instructions http://en.wikibooks.org/wiki/SPARC_Assembly/Arithmetic_Instr... Back in the late 1980's, a Sun employee jokingly pointed out that because the DECstation used the MIPS processor in little endian mode (it supported both big and little endian) to match the VAX, its processor should be called the SPIM. I asked if the SPARC supported little endian mode, would it be called the CRAPS? He was flustered, and told me to shut up and never tell anyone that SPARC spelled backwards was CRAPS.
- ScottBurson 12y agoHi Don! I'm afraid TADDCC has gone the way of the dodo -- the 64-bit SPARCs don't have it.
- DonHopkins 12y agoWhich way did the D0D0 go???! There are much worse ways to go -- like the way of the Oracle, for example. ;(
- lispm 12y ago> Almost every programming language uses 64-bit integers on typical modern Intel machines. That's not true. Most implementations which use a GC and/or are dynamically typed will have less than 64bit integers.
- arh68 12y ago> Could we have a solution which would keep ints unboxed but have fast arithmetic operations? Wait, is the answer not floating point? Using 64-bit IEEE 754 means the lower 52 bits (51-0) are significand, and bit 52 is implicitly 1, so setting bit 0 to keep track of GC stuff only introduces an error of ~1/2^52. Floating-point multiplication isn't as fast as integer ALUs, perhaps, and you're now limited to 52-bit integers, but that's what Lua does and it gets by fine.