How OCaml Makes Ints Speedy | Prime Reacts
HTML-код
- Опубликовано: 8 сен 2024
- Recorded live on twitch, GET IN
/ theprimeagen
Blog article: blog.janestree...
Written by: Vladimir Brankov
MY MAIN YT CHANNEL: Has well edited engineering videos
/ theprimeagen
Discord
/ discord
Have something for me to read or react to?: / theprimeagenreact
Hey I am sponsored by Turso, an edge database. I think they are pretty neet. Give them a try for free and if you want you can get a decent amount off (the free tier is the best (better than planetscale or any other))
turso.tech/dee...
As someone whose software user count could totally be represented with a boolean value, I've never felt so roasted in my life. 😂
"Is THE user logged on"
So you have a true project and a false project. Sound like enough. Don’t know why you’d need more.
At least it's not void!
I know this is a joke but...
The smallest unit in memory is a byte so you can have up to 255 users even with a boolean.
My friend was exactly my 69th GitHub download (for that release) so I'll call that a win any day of the week lol
Discussion of how programming features translate to binary and assembly are the perfect way to start a morning.
Yes discussion are perfect.
10:45 Ackchyually, arithmetic shifts keep the sign bit and shift the other bits. They do not rotate. Logical shifts treat the sign bit like any other bit.
kinda shocked they got this wrong honestly. Understanding the difference between arithmetic and logical bitshifts is necessary is just basic low level C and the entire point of an arith shift is to keep the sign bit constant for arithmetic checks, so a right shifted negative number will always stay negative and a logically shifted negative number will be positive. (since the sign bit gets flipped to 0)
With that said IIRC an arith shift *_does_* still shift the sign bit, the difference is just that it fills the new bits with 1s instead of zeros. I remember I used that to fill a block of memory with 1s a few times with what I thought of as a "bitrip" in that I'd take a single bit, 0000 .... 0001, do a 63 bit left shift (or 31 or whatever) to get 1000 ... 0000 and then do an equivalent right shift of the same number of bits but, if the number is a signed integer, right shifts are arithmetic so since the "sign bit" is now 1 it would fill the entire memory block with 1s. Ripping a single 1 from one side of the bitstring to the other and back again can be used to fill entire block with all 1s. Don't remember the exact reason why I did this over something else, might have been portability or something. In any case the difference between an arithmetic and a logical shift is pretty massive so, while I could understand a typescript guy not knowing it, (yes I know that's reductive I'm just making a point) it's kinda weird for a channel literally called low level learning to get it wrong. I wonder if different CPU architectures treat it differently or something and that might be what's causing the confusion. Still though, given the entire point of an arithmetic shift is to keep the sign constant, it'd be weird for any architecture to loop around with an arithmetic shift since that wouldn't necessarily keep the sign bit constant, meaning it just wouldn't be useful for arithmetic operations. (it'd have other uses sure, but why call it an arithmetic shift if it's not doing anything useful for those arithmetic purposes and is instead doing something entirely different?)
I do all of my math with 8192 bit integers. Just for the extra precision in leading zeros
There is a method for avoiding tagged ints in a garbage collected language. Essentially the compiler inserts a mask alongside the data itself that signals which values are ints and which are pointers. Then the garbage collector looks at the mask (which could be at the top of every function's stack frame) to determine which pointers to follow. Similarly, every record on the heap has a mask indicating which fields are ints and which are pointers.
I'm a little disappointed the article doesnt mention this technique and the trade-offs that made them choose tagged ints
I think it was the right tradeoff for 32-but OCaml. Every memory block has 8 bits for the tag (variant/enum constructor or some reserved special values), and 22 bits for the size. It would be sad to sacrifice an extra word for the mask, or have a significant size restriction on block size (e.g. array length). 64-bit OCaml now has 54 bits for the size, which is arguably overkill, but probably not worth fundamentally rewriting the runtime.
I think it was the right tradeoff for 32-bit OCaml. Every memory block has 8 bits for the tag (variant/enum constructor or some reserved special values), 2 bits for the GC “color”, and 22 bits for the size. It would be sad to sacrifice an extra word for the mask, or have a significant size restriction on block size (e.g. array length). 64-bit OCaml now has 54 bits for the size, which is arguably overkill, but probably not worth fundamentally rewriting the runtime.
someone in chat asked, why don't they just use the most significant bit? I think this is because an integer overflow could happen and unpredictably overwrite the bit, whereas the least significant bit doesn't have that problem (but you have to adjust all the arithmetic operations as shown)
Also, this way no shifting is required to word align the pointer.
Right, the least significant bit of a pointer is always 0, but the most significant may not be.
Thanks for taking time to work through that bit operation, super helpful for me.
13:00 that's the caveat for implementing this sort of thing into the core language, you never know when processor manufacturers pull the plug on your niche instruction set.
I run into the ‘period & quotes’ problem daily. If I’m trying to indicate a programming term or variable name by enclosing it in punctuation, then I don’t want to include a period-regardless of which is correct. I would rather avoid confusion than be correct, which is rarely the case tbh
@Prime, You really should take the time to learn assembly. It will give you so much more insight into the inner workings of computers.
X86-64 would be the obvious choice, but RISC-V would be much faster to learn. Once you fully understand one architecture, it’s easy to learn the others.
You could even make a series where you write a RISC-V assembler/emulator in Zig. That would be very helpful for the young people watching. I actually have thought about doing that for my learn Zig project, but I’m not a youtuber.
I wrote a lot of 6502 assembly in the ‘80s and even though I haven’t written much assembly since, it has helped me a lot when writing code in high level languages.
Btw. Logical Shift Left means you zero extent the result. You usually have LSL, LSR and ASR. The two latter are Logical and Arithmetic Shift Right. The Arithmetic version copies the sign bit in from the right and the Logical version copies in zeroes in the most significant bits.
Can you imagine these channels shilling ISA's the way they shill languages? I use Itanium btw
@@idiomaxiom That would be hilarious.
RISC V is the only one reasonable isa to learn these days. But looking at assembly is always useful since it gives you an idea of how complex to execute the function will be on the cpu.
@@nikolausluhrs I use Arch fully re-written in Rust on RiscV btw
X86 still reigns supreme and if RISC-V is ever a serious competitor to ARM, they’ll just start dropping prices.
Apple, Qualcomm, etc. aren’t just gonna jump ship and high performance, robust and generally well designed chip don’t just appear from nothing, because you’ve got a free ISA.
Don’t get me wrong, I love RISC-V and if your doing microcontrollers or similar embedded development it’s definitely worth at least checking out. But it’s still at least a few decades away from being “The only one reasonable ISA to learn”, even if it were on the fast track to tacking over literally everything.
Logical shifting simply pads the shifted value with zeros. Arithmetic shifting will preserve the signed bit. Rotating left/right, is usually it's own cpu instruction and is not the same as shifting.
I have two comments:
Logical shift is, as you said correctly, a zero-fill.
Arithmetic shift is sign-extension, not rotation, (i
e. for right shift fill with the most significant bit (the sign bit)).
For left shift, arithmetic shift is equivalent to logical shift, so it usually isn't implemented.
Other than that, I don't understand why they use a logical one to indicate an int. A logical zero would be more efficient:
x + y becomes x + y
x * y becomes x * (y >> 1)
x / y becomes (x / y) > 1)
(note: I would assume the use this to ensure that null pointers are zero, but using 1 as the null pointer would seem fine to me)
pointers are aligned memory addresses so they're a multiple of some number, usually a power of two, so their last bit is *always* 0, leaving you to use that bit as a flag for some other usage - ints in this case
@@aonodensetsu I think the idea would be to invert that flag: 0=int, 1=pointer.
You'd save the extra work on integer math operations, at the cost of having to do something similar for reference/dereference operations. Was one of my first thoughts as well (particularly looking at the definition for division).
I can only assume/hope that the designers would have thought of that and made an educated decision that the performance hit tradeoff was better when its the ints are flagged. (No idea how that'd be measured but it feels like something you could compute with a moderate sample of popular software and some cleverness.)
IIRC some arch like arm have barrel shifters inline with the APU so it’s trivial to precondition these values. Kinda cool. More interesting is what happens when you do vector operations 🤔
logical shift is just zero fill, but arithmetic shift fills with the sign bit so negative numbers are preserved.
rotation is a different thing entitely from my understanding
edited - put em the right way round (easy to forget tbh)
I was surprised they didn't know.
I think you mixed up arithmetic shift with logical shift.
@@CrazyMineCuber Seconded, arithmetic preserves the sign, no?
@@CrazyMineCuber maybe tbf took the class last semester
You have arithmetic and logical shift backwards. Arithmetic shift right maintains the sign bit
"You can count your users with an 8-bit integer". Savage, lol.
If a 32 bit integer is enough you could store a 64 bit value (the upper half being the header and the lower half being the integer) in rdx (64 bit register) and use edx (32 bit register, addresses the lower half of rdx) to do normal arithmetic on the ineger.
Wouldn't that clear the higher bits, though?
@@Zooiest No, if you're using instructions on the lower 32-bit register parts, the higher bits are not affected.
@@0xAxXxByeah because registers were built incrementally when x86 evolved. Each time they widened registers, but kept old instructions for manipulating LSBs.
@0xAxXxB
@foxcirc
No you cant. Operations on the smaller register clears the upper bits unless you use special instructions which specifically state they dont.
00007FF93F5E0911 | 48 B8 00 00 00 00 FF FF FF FF | movabs rax,FFFFFFFF00000000
00007FF93F5E091B | FF C0 | inc eax
rax == 0000000000000001
I think x + y + z would become x + y + z - 2, and in general you subtract 1 for every addition, add 1 for every subtraction
Ignore my last comment lol. I misread yours. You're correct, this is true by induction.
You can have pointers to values held in the stack. Pointers are not used exclusively for heap memory.
Of course, If I said that, I misspoke
I haven't watched the entire video (minute 4) but this is called pointer swizzling, it surprises me that this term isn't mentioned yet
Do garbage collectors not maintain a data structure of allocated memory with types associated? So that you wouldn't have to differentiate ints and pointers by value alone?
OCaml uses a single tag bit to differentiate between ints and pointers, but does not store any type information as it is removed during compile-time. This is also what the article explains (tagged ints)
That's also how Ruby stores small integers (between -(1
2:22 Oh, I didn't know that's a thing in America. I was wondering why deepl put the dots inside the quotes and put them outside maually.
I think it's different is someone says something. In these cases I'd most likely put the symbol for ending the sentence in the end of the quote, but still inside, especially if it's a questionmark or exclamation mark.
Here to be `that guy' and correct the assertion that "arithmetic shift rotates".
An "arithmetic" shift differs from a "logical" shift in that the operand is treated as a signed integer, thus preserving arithmetic correctness. The distinction is meaningless for left shifts (on x86 at least) meaning if you shift left, say, an int8 containing -128 (0b10000000) you get 0 and you're SOL (kinda... after a left shift by 1-bit, you can check the Overflow flag to detect if the sign bit changed).
An arithmetic right shift preserves the high (sign) bit, copying it in to the "empty" bits - so if we arithmetic right shift our -128 example by 3 (ie, divide by 8), we get 0b11110000 = -16. A logical right shift treats the same binary 0b10000000 as +128, shifting right by 3 = 0b00010000 = 16.
In addition to these 4 kinds (well, 3 technically) of binary shift, you have rotation left and right (rol, ror), which is exactly what it sounds like. There is no "arithmetic" property to preserve in such an operation, so these are purely "logical" binary operations. But there is one more twist.
The binary shift operations write the last bit shifted off the operand into the "carry" flag. On the x86 there are arithmetic (eg: adc, sbb), conditional (eg: set[n]c, cmov[n]c), and logical (eg: rcl, rcr) instructions which incorporate the carry flag. The relevant ones here being "rotate with carry" left / right (rcl, rcr).
These instructions extend your operand virtually by 1 bit (the carry flag). So if you "rotate with carry left" on your int8 operand, it becomes an int9 with the carry flag in bit 0, the bits are rotated through the specified number of positions, and your int8 result is the top 8 bits of the virtual int9. With rcr the carry flag becomes the high bit.
On x86 there are also bit shift operations that don't touch the flags. This is useful for certain modular arithmetic calculations (think cryptography).
we need RAM with automatic dereferencing.
this is a classic optimization that a lot of dynamic languages have used, Common Lisp is full of this type of optimizations especially due to code being a Recursive Single Lists
logical vs arithmetic shifts are only different when shifting right. asr maintains the 'signed' (top) bit when shifting right, lsr does does not. asl & lsl are synonyms.
Ruby also represents ints this way (btw)
Fullstop/period inside the quote marks was apparently just to look better even though it wasn't logical. I'm not sure if it was supposed to look better mainly in typesetting, handwriting, typing, or all of them. People just memorized it as an absolute rule though with no reasoning or explanation, which made it one of those religious arguments.
One thing that is going to confuse a lot of people here is that saying "pointers are word aligned" is kind of a sloppy way to describe it. The crucial thing is that the DATA is word-aligned, which is why the ADDRESSES that the pointers point TO are guaranteed to never have the low bit set.
The pointers themselves may be word-aligned too, but phrasing it this way makes it sound like that is what somehow makes the low bit predictable.
Comparing this to C# I don't get at all why this is necessary. Just from the article and with none of the context of OCaml C# has all of the listed benefits with none of the drawbacks. In fact so does F# which is similar to OCaml in other ways.
I guess Java uses this stuff since ... ever. Every memory allocation is aligned to last 3 bits, meaning aligned by 8 in 64bit JVM. And aligned to at least 2bits, meaning aligned by 4 in 32bit JVM. So they could use those bits for ... stuff. For example marking the pointer as visited/not visited by garbage collector. Color in red-black tree. Distinguish pointer to boxed integer / float vs in-place integer / float as mentioned here in OCaml case. Java on 64bit OS could be configured to use 32 bit pointers, if each pointer is aligned to (lets say) 4 bits, that would give limitation of max 64 GB RAM heap, but each pointer (object reference in Java speak) would be half the size, meaning both processing speed and memory consumption optimization. Similar JavaScript in V8, they are using few lowest bits for similar shenanigans. Similar Ruby. And I guess every interpreted language. (I never looked inside Python interpreter.)
Like almost every innovation relating to optimisation of VMs, this was pioneered by Self, then adopted by JavaScript, and now it seems Ocaml.
Not to downplay Self, but Smalltalk pioneered optimizing JITs and inline caches, and dynamo pioneered trace optimization.
Common lisp compilers have done this for a while, not 100% sure if they got it from self or figured it out on their own.
69-bit int otherwise its a scam
you can use 69 bit integers in zig B)
8:12 evil discord sound
I'm not sure I understand why this is needed in Ocaml. Surely as a statically typed language (with some beautiful type inference capabilities), the compiler could know whether something is an integer or not at compile time, without any runtime checks? Like, this is why C++ doesn't need anything like this, even though it does something very similar with small string optimizations, because strings are a variably sized type and need to go on the heap.
Haha use a Boolean for number of users… so true! 😂
I don't get it why they don't use oldest bit as the flag, it wouldn't affect arithmetic then.
For pointers it would either reduce possible adress space or addressed could be shifted left before aceesing
Shifting pointers would kill performance. Reducing address space is usually not possible, as it is dictated by the operating system.
Loved the convo! It's great to see more low-level OCaml content out there. I recently did a deep dive into the runtime representation of OCaml values but in contrast to what the post says, I haven't seen a 2x perf difference between OCaml and C arithmetics. It's true though for boxed OCaml Int64s and floats.
The post is old though, perhaps things got outdated? Alternatively my benchmarks might be borked 🫠 however, gcc now compiles int addition as `lea` too (same as OCaml), so not sure...
Link to the relevant part: ruclips.net/video/EblI_VXaeIk/видео.html
Great episode.
16:32 the main crux of the vid for me - to say in 1 word whether it an int or not.
how does c do it then?
For optimal CPU Feng Shui you really want about 61.8034 bits.
American "something." is like writing code like this:
fn american() {
f(
})
the dot inside a quote is for sentences, for a single word it's outside
American English convention (at least as I was taught it in school) is that all punctuation always goes inside the quotes, without exception. But I say "yuck", and don't use that convention. Unlike the "yuck," that I was taught to write. But (thankfully) this convention appears to be changing over time with more american people using the British rules for punctuation.
@@KirkWaiblinger well that's what I learned in school lol, if it's just convention then it's not a set rule anyways
@@cheebadigga4092 i mean, convention becomes rule when your elementary school teacher marks you down for not following it lol.
@@KirkWaiblinger that makes sense lol
"Intel CPUs might have changed in the last ten years" ... like AMD exists again 😉
This is one of the things I don't like about OCaml. Since the compiler has all the information at compile time, this could totally be avoided.
Could someone explain the bitshift example? He said that x
Short version, x
@@ShmingsThings Ok, I think I got it! The | 1 meant that x was being (or'd?) with the value of one in binary. Sweet, thanks for the reply!!!
No sane person uses strings for numbers in finance. Usually int64 plus byte for exponent
In the specific space of electronic Turing machines, *there is no other type than integer.* Everything is an integer. All other types are simulated.
If there's something you can't program using only integers, you can't program it at all. 🙄
i have no experience with ocaml, but is it because theres some kind of any type, and so you want to know whether a value is int or not via something like instanceof? because if types are compile time or using tagged values im quite certain you need none of this
You are right. That said for parametric polymorphism sometimes you can't always pass unboxed values into them. Hence the compiler may need to pass boxed integers to the function despite knowing its a int64 or whatever.
@@thomassynths yeah thats how java has int and Integer
"Almost every programming language uses 64 bit integers" really? I thought 32-bit would've been more popular, 64 just available. I recall the unorthodox bit decoding can be a bit complicated, didn't someone try it in the past with 7 bits and caused an annoying bug?
Btw "boxed." is not a sentence. It doesn't end with a period. It belongs in the outside. Unless.
Fuck I love this
Does OCaml also use tagged pointers for sum types?
For some of them, yes. For simple ones e.g., 'type colour = R | G | B', these are represented in memory as ints 0, 1, 2, so no need to box. For more complex ones like 'type number = Zero | One_plus of number', the 'One_plus' variant needs to be boxed.
@@yawaramin4771 Thanks for the response! If bit #0 is reserved for what the video is about, couldn't bits #1 through #7 still be used to include the tag in the pointer on a 64-bit architecture? Say, encode Zero as 0b10 and One_plus as pointer | 0b100.
Opinions can be objective.
Aperently they changed it abit
Unnecessary BS of languages, instead of taking advantage of a Hardware Feature, that's going to be way faster and better, as it has 64-bit, and not just 63-bits. O'Cmon!
Hot take, correct grammar doesn't exist lmao
First gang
second