81–90 of 98 posts
Last time this came up ( https://news.ycombinator.com/item?id=20808778 ) and disappeared almost instantly, I wrote: A discussion of systems programming optimization that doesn't start with single-writer ring buffers starts on the wrong foot. Those other tricks are excellent, and I use all of them, in cases where they work at all. But, e.g., seeking a way not to need to take a lock at all should come before discoverin…
Earlier quoted context omitted.
That’s nice rhetoric but I didn’t pick the survivor examples.
You did, by mentioning the companies that are alive and kicking. OTOH DEC placed a bet on new and cool Alpha architecture, and died switching (bought by HP).
DEC was acquired by Compaq not HP. Compaq was later acquired by HP but before that happened Compaq sold the Alpha line to Intel because it would have competed with the Itanium. The Alpha was then licensed by Intel to the Chinese (according to Gustafson) and was used as the basis for the Sunway Taihu Light.
Can I help you with anything else?
Earlier quoted context omitted.
Armv8 has an opt-in feature you can turn on to ignore the top byte: https://en.wikichip.org/wiki/arm/tbi This is also where the pointer authentication code goes for arm pointer authentication: https://lwn.net/Articles/718888/ On x86_64 and arm without those features enabled, the top bits of the pointer must be sign extended. This means that x86_64 by default gives you the top two bytes to play with as long as you don…
"Attempting to access a pointer whose top 16 bits aren't a sign extension of bit 48 will fault." Currently. Coming soon to an Intel chip near you is 57-bit virtual addressing and 5-level page tables [1]. It would be quite a bug that would only crash on new Intel hardware on probably quite full memory maps where your pointer fix up code wouldn't restore bits 48-57 correctly. [1] https://www.phoronix.com/scan.php?page=…
Yeah, I'd hope that code that uses such tricks would have an error check for pointers that use the bits it wants to use. Better a clean crash than corruption.
It'd be neat if a program could tell the OS what address range is acceptable. Linux has mmap(..., MAP_32BIT, ...) but obviously that's pretty limited. Maybe something like map(addr, ..., MAP_MAXADDR, ...) which would tell it addr represents the maximum acceptable address to return. So if you intend to use the top 16 bits, you could tell it this mapping can't use those.
Edit: oh, actually, I see they do something kind of like this. https://lwn.net/Articles/717293/ "An application that needs [virtual address beyond 48-bits], and which does not play games with virtual addresses, can provide an address hint above the boundary in a call to mmap(), at which point the kernel will understand that mappings in the upper range are accessible." Still not quite as flexible as I was imagining but not bad.]
Earlier quoted context omitted.
Can't you just make sure that your allocator only uses the bottom x bits? (Of course you still need to be careful when interfacing with code that maps memory in some other fashion)
If your allocator calls mmap or an equivalent, and the OS gives you back a pointer that uses all 64 bits (or more than 48, anyway) then what do you do? I guess the allocator has to retry and pray, or maybe just give up and fail. In any event your clever code is not going to work well, since you have made a choice that is non-portable. I imagine that the guy on the MacOS team who stuffed some desk accessory bits into…
In most cases your compiler should do the clever work of turning your division or modulo operation into easier to do bit banging... but only if you're operating on a reasonable constant. Powers of two are best but you can do other constant divisions by stringing together 1-latency operations in ways that are still far faster than division.
If your hashtable dynamically resizes though, (x % size) will use a full divide. You could keep the log2 of the size around instead, and rely on (x % (1U https://godbolt.org/z/HbGnJH) but (x & (size - 1)) might be easier at that point.
> Part of why the change couldn’t be enabled by default is because various high performance programs, notably various JavaScript engines and LuaJIT, use this repurposing trick to pack some extra data into pointers. Does any one know if this sentence can be backed up by a citation? I know that the NaN-tagging trick assumes that pointers have 48 bits (small enough to fit inside a floating point mantissa), but was this…
The issue listed was definitely a concern, but was worked around by having the kernel only allocate userspace linear addresses that aren't 48-bit-canonical in response to a mmap() call that supplies such an address as the hint argument. See the commit message in this commit for example: https://lore.kernel.org/patchwork/patch/796025/
So for a program to get an address above the 56-bit limit, its memory allocator has to specifically indicate to the kernel that it supports that.
"Repurposing Top Bits" - don't do that. Honest. The IBM 360 shipped with 32-bit addresses but only 24 bits decoded. "Hey, there's a whole byte up top that nobody's using today, let's put some stuff there!" When they wanted the address space IBM found themselves architecturally hamstrung, and the cost to dig out was significant. The 128K Macintosh used a 68000; it had 32-bit addresses but only 24 bits were decoded. "H…
The responsibility for this lies not with just the programmers, but the address decode logic. The hardware should have seg faulted on non-zero upper bits (which would have required the addition of a few OR gates, hardly a problem).
So to use these dirty tricks successfully, you have to mask out those bits before you dereference your pointer.
Earlier quoted context omitted.
bitmapped set is one I don't remember at all. It have another name? A quick google not give me a clear idea of what is or how could be usefull...
std::bitset is one. But you can just use an unsigned int, or array of them. In C++ or C, set intersection is &, union is |, complement is ~. Cardinality is __builtin_popcount, or std::bitset ::count(). Membership test for m is (s & (1 >5] & (1 Bitsets are useful in more places than you might guess, because they can be used to filter out, with typically a single instruction, a majority of uninteresting cases in search…
Hey, do you have a reference for that? I've been doing some research into Leibniz's calculators, and I've been finding few sources.
> The Magic Power of 2: Division Is Slowaloo Is LLVM not smart enough to optimize this?
Yes, for constant divisors. However, for signed division, the C semantics (round towards zero) are different than the semantics when you apply an arithmetic shift (round towards negative infinity). If you are fine with the latter behavior explicit shifts remove several extraneous instructions dealing with the difference.
> Now, to support multiple processors on a single machine reading and writing from the same memory in a coherent way, only one processor on a machine can have exclusive access to a given cache line. Does this also apply when multiple processors are only reading memory?