91–98 of 98 posts
Are there any golang implantation a of high performance hash maps? Does the the standard lib do this?
But “high performance” is not a single dimension - if you say a bit more about what you care about, maybe another choice would fit.
Earlier quoted context omitted.
"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=…
It'll probably be quite a while before operating systems rush to turn on extra level of page walk fun, increasing TLB miss penalty even more. If only x86 could have 64 kB pages... Of course you're right it's not a great idea to use those bits. Eventually they will be in use, although it's probably 10+ years.
Earlier quoted context omitted.
It'll probably be quite a while before operating systems rush to turn on extra level of page walk fun, increasing TLB miss penalty even more. If only x86 could have 64 kB pages... Of course you're right it's not a great idea to use those bits. Eventually they will be in use, although it's probably 10+ years.
Isn't the tendency to use more and more large pages (1MiB) on x86 anyway? And then just use user space allocators to split them up for malloc.
"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…
Meh, when you get to the point where you're exceeding your available address space, there's probably a million other refactorings you had to make to address all of the other architectural changes.
I don't remember how many Mac applications were '32-bit clean' and ran without modification when VM was turned on. I do know that some apps had to do significant rework, and that there was a whole generation of abandonware where developers didn't think it was worth the effort and just walked away from their customers.
Earlier quoted context omitted.
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…
>Leibniz (inventor of calculus) used this method very heavily in his own work. Before computers--and even into the 1960s--it was the most important way of automating data processing. Back then, you used cards that had a row of either holes or notches along one edge, and selected matching cards from a stack by inserting a rod through the stack at a selected spot, and lifting. Hey, do you have a reference for that? I'v…
I think I found out about Leibniz's bitwise activities in Neal Stephenson's Quicksilver, but he invented the modern notions of both sets and digital logic, according to Wikipedia. He would have used the cards in catalogging libraries.
"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…
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…
Earlier quoted context omitted.
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…
Yup I used bit sets to write a super duper fast Sudoku solver. For examples you can detect naked singles extremely fast by just and-ing the bitsets in a given row, column or house, taking the complement, and checking if a unique bit is set.
But they used to be essential for automating chess. A 64-bit word represents a board, and a set of words represents the positions of each type of piece, one word for white pawns, etc. Another word shows places threatened by the white pawns, and ORing them shows all the threatened places.