Should really give the big-O notation for common operations for comparison of the approaches.
---
There are some variations of Chunk/Bucket arrays which offer different characteristics.
HAT (Hashed Array Trees[1]) are close to what is presented - the index block is always a power of 2 and points to data blocks of the same length - ie, it increases as: 1x1, 2x2, 4x4, 8x8, 16x16, ...
The downside is each time the length reaches a new power of 4 it requires the data to be shuffled about, which may cause latency spikes.
RAOTS (Resizeable Arrays in Optimal Time and Space[2]) is a variation where the index block block is approximately the square root of the length. It increases by adding a new block and resizing only the index block. The old blocks remain part of the structure and don't need reshuffling like HAT, which avoids the latency spikes, but there are more individual allocator calls. However, blocks are always a power of 2 which makes them arena-friendly.
Both of these have O(1) element access and waste only O(√n) space, which makes them quite optimal for uses where memory may be a constraint.
---
In the double-and-copy style array, one trick is we can avoid storing `capacity` and compute it on demand - determine the MSB of the length (using `lzcnt` or `bsr`), and then determine the next power of 2 sufficient to hold that length. In C23, this is `stdc_bit_ceil` (<stdbit.h>).
In the "Xal" structure (which has several other names), we can use `stdc_first_leading_one` to determine the index in the index block, then zero out the leading one bit to determine the index in the bucket.
This structure would be more efficient if processors provided a `log2mask` instruction which computes both the MSB and the remainder after masking the MSB in one instruction. (Similar to how `divmod` instructions work where the quotient and remainder are both computed in one instruction).
Thread locals don't fully solve the problem. They work well if you immediately call the closure, but what if you want to store the closure and call it later?
Because we create `reverse_sort` between creating `normal_sort` and calling it, we end up with a reverse sort despite clearly asking for a normal sort.
> x86 is unusual in mostly having a maximum of two operands per instruction[2]
Perhaps interesting for those who aren't up to date, the recent APX extension allows 3-operand versions of most of the ALU instructions with a new data destination, so we don't need to use temporary registers - making them more RISC-like.
The downside is they're EVEX encoded, which adds a 4-byte prefix to the instruction. It's still cheaper to use `lea` for an addition, but now we will be able to do things like
It's due to the way the instruction is encoded. `lea` would've needed special treatment in syntax to remove the brackets.
In `op reg1, reg2`, the two registers are encoded as 3 bits each the ModRM byte which follows the opcode. Obviously, we can't fit 3 registers in the ModRM byte because it's only 8-bits.
In `op reg1, [reg2 + reg3]`, reg1 is encoded in the ModRM byte. The 3 bits that were previously used for reg2 are instead `0b100`, which indicates a SIB byte follows the ModRM byte. The SIB (Scale-Index-Base) byte uses 3 bits each for reg2 and reg3 as the base and index registers.
In any other instruction, the SIB byte is used for addressing, so syntax of `lea` is consistent with the way it is encoded.
It's not only xor that does this, but most 32-bit operations zero-extend the result of the 64-bit register. AMD did this for backward compatibility. so existing programs would mostly continue working, unlike Intel's earlier attempt at 64-bits which was an entirely new design.
The reason `xor eax,eax` is preferred to `xor rax,rax` is due to how the instructions are encoded - it saves one byte which in turn reduces instruction cache usage.
When using 64-bit operations, a REX prefix is required on the instruction (byte 0x40..0x4F), which serves two purposes - the MSB of the low nybble (W) being set (ie, REX prefixes 0x48..0x4f) indicates a 64-bit operation, and the low 3 bits of low nybble allow using registers r8-r15 by providing an extra bit for the ModRM register field and the base and index fields in the SIB byte, as only 3-bits (8-registers) are provided by x86.
A recent addition, APX, adds an additional 16 registers (r16-r31), which need 2 additional bits. There's a REX2 prefix for this (0xD5 ...), which is a two byte prefix to the instruction. REX2 replaces the REX prefix when accessing r16-r31, still contains the W bit, but it also includes an `M0` bit, which says which of the two main opcode maps to use, which replaces the 0x0F prefix, so it has no additional cost over the REX prefix when accessing the second opcode map.
> It's not only xor that does this, but most 32-bit operations zero-extend the result of the 64-bit register. AMD did this for backward compatibility.
It's not just that, zero-extending or sign-extending the result is also better for out-of-order implementations. If parts of the output register are preserved, the instruction needs an extra dependency on the original value.
Except for `xchg eax, eax`, which was the canonical nop on x86. Because it was supposed to do nothing, having it zero out the top 32-bits of rax would be quite surprising. So it doesn't.
Instead you need to use the multi-byte, general purpose encoding of `xchg` for `xchg eax, eax` to get the expected behavior.
The primary focus of Lions/seL4 is security, and formal verification of it. It's a necessary project for a world where CVEs are frequently published for the Kernel and other underlying system services, in part because they're still using a 1970s OS design which didn't have internet-connected computers in mind.
The seL4 kernel uses an Object-Capability system (ironically which have also been around since the '70s) in place of Access Control Lists used in POSIX systems. The idea behind capabilities is "don't separate designation from authority" - the capability is both a designator of a resource and the authority to use it - there are no separate ACLs. Separation of designation from authority leads to confused deputies - where one process with lower privileges can trick a higher-privileged process to use the higher privileges on its behalf, which very often leads to privilege escalation vulnerabilities (ie, RCE as root).
Each process has a "cspace" (Capability Space), which holds the capabilities the process may use. When the process performs a system call, it references a capability slot from a set of tables in its own cspace where the capability is held, and the Kernel verifies that the capability is valid in order to perform the syscall. The capabilities can be revoked at any time, and importantly, they cannot be forged - only delegated.
Additionally, seL4 is a microkernel design which is intended to have a small attack surface. It provides only a small number of system calls like `Send`, `Recv`, `Yield`, and combinations of, such as `Call`, `Reply`, `ReplyRecv`. It's a generic interface where an IPC buffer is passed along with a set of delegated capabilities, but there's no specific calls such as `SYS_write` or `SYS_mmap` - these are built on top of the `Send`/`Recv` syscalls and their services are provided by other user-space daemon processes.
One of the best developments of seL4 is the "Mixed-criticality system" support, which provides capabilities for processing time - to enable some processes to have real-time support without becoming CPU hogs.
seL4 can also be seen as a hypervisor which can virtualize other kernels, and part of the Lions effort is to be able to utilize Linux drivers using isolated Linux guests.
We could potentially use a conditional move and an unconditional jump to make the branch target predictor do the work instead - and flood it with a bunch of targets which are intended to mispredict. Eg, we could give 255 different paths for abandon and select one randomly:
Assuming no inherent bias in the low byte produced by `random`, there's only a ~1/255 chance that an abandon branch will correctly predict, though this is also true for the send branch. The conditional branch in send though should only mispredict 1/256 times (when random returns 0).
If we're sending significantly more often than 1/256 calls to resolve, it may be possible to train the BTP to prefer the send branch, as it will correctly predict this branch more often than the others which are chosen randomly - though this would depend on how the branch target predictor is implemented in the processor.
rand() doesn't do what you think it does. It's a multiply then an add, then return particular bits of the current seed. See "Linear congruential generator" for more information.
On GCC, it's multiply by 1103515245 then add 12345, and return low 30 bits. On MSVC, it's multiply by 214013 and add 2531011 then return bits 16...30.
I don't specifically mean stdlib `rand` (hence comment about assuming no inherent bias) - but just some arbitrary PRNG. Updated the code above to say `random` so as not confuse.
The branch taken hint (3EH) was re-added in Redwood Cove (2023), but it's only for static prediction where the branch predictor has not yet encountered the branch - ie, useful for things you would only use once or twice but would likely take the branch. Once the branch predictor has some information the static prediction hint is ignored, so it's best to omit it for anything that will eventually have dynamic branch prediction (ie, run many times), because you'll be consuming bytes in the i-cache which serve no purpose.
It's most likely a combination of both genetics and society - neither are absolutes. There is no concrete evidence that intelligence is purely a social construct, nor that it is genetic. We simply don't know.
People get cancelled not for saying that it is genetic, but for questioning whether it may be. Of course, we will never know if we're not allowed to ask. Cancel culture is anti-science.
Watson may have been racist, but questioning whether there is a relationship between genetics and intelligence by itself is not racism.
We are allowed to ask this question, and we have asked it, and we've found that the evidence does not validate the premise of inherent racial intelligence or other racial essentialist views[0]. Claims like "Asians have the highest IQ" are not meaningful or scientifically valid.
This (https://nces.ed.gov/fastfacts/display.asp?id=171) US-government provided table of average SAT scores in the United States in 2023, which has breakdowns by race/ethnicity of the test-taker, and clearly shows Asians with the highest average score out of any of the racial categories in the chart, is evidence for something that you could pithily summarize as "Asians have the highest IQ". The relationship between SAT scores and IQ and intelligence in an everyday sense; and how representative people whose racial categorization went into this chart are of everyone on the planet who could also be grouped into that racial category; are more complicated questions. Nonetheless, the hypothesis that there are genetic differences between people of different racial groups that affect their intelligence in a similar way to how they affect more obvious racial correlates such as hair and skin color, is not obviously wrong.
> This US-government provided table of average SAT scores in the United States in 2023
If you look at their source[0], there's no information about how they controlled for confounders (because it's impossible as they acknowledge[1].)
There's a strong correlation between "education of parents" and "SAT score"[2] which implies that family wealth is a strong contribution to a child's SAT score (something we all know anyway); that's also backed up by [3].
(I'd suggest that [4] also contributes to the positive correlation between familial wealth and test scores but perhaps in a more oblique "the higher goals are aimed at by kids who have the backing to contemplate them because of family support structure, tutoring, ability to pay for the degree(s), etc." way.)
(Similarly for [5], I suppose - there's a distinct correlation between what I'd say was "perceived difficulty of major" and the mean SAT scores. Again probably down to familial wealth, support, tutoring, etc.)
Someone who's an actual statistician would probably rip this apart much more thoroughly and with more rigour than I, of course.
[1] "Relationships between test scores and other background or Evidence-Based
Reading and Writing (ERW) and Math contextual factors are complex and
interdependent. Caution is sections of each assessment in the SAT Suite:
warranted when using scores to compare or evaluate teachers, schools,
districts, or states, because of differences in participation and test
taker populations."
[2] Bottom of page 4: "Highest Level of Parental Education"
No one is claiming that intelligence isn't genetic. Certainly not "the left."
The claim is that race as commonly understood and defined (specifically by eugenicists like Watson) has no genetic basis, and therefore claims which follow from that definition such as "Asians have higher IQ" are not scientifically valid, and do not prove the validity of Watson's racial views.
For some reason sparkie just decided to reframe my comment around a claim I didn't make and now here we are litigating a "leftist" strawman.
---
There are some variations of Chunk/Bucket arrays which offer different characteristics.
HAT (Hashed Array Trees[1]) are close to what is presented - the index block is always a power of 2 and points to data blocks of the same length - ie, it increases as: 1x1, 2x2, 4x4, 8x8, 16x16, ...
The downside is each time the length reaches a new power of 4 it requires the data to be shuffled about, which may cause latency spikes.
RAOTS (Resizeable Arrays in Optimal Time and Space[2]) is a variation where the index block block is approximately the square root of the length. It increases by adding a new block and resizing only the index block. The old blocks remain part of the structure and don't need reshuffling like HAT, which avoids the latency spikes, but there are more individual allocator calls. However, blocks are always a power of 2 which makes them arena-friendly.
Both of these have O(1) element access and waste only O(√n) space, which makes them quite optimal for uses where memory may be a constraint.
---
In the double-and-copy style array, one trick is we can avoid storing `capacity` and compute it on demand - determine the MSB of the length (using `lzcnt` or `bsr`), and then determine the next power of 2 sufficient to hold that length. In C23, this is `stdc_bit_ceil` (<stdbit.h>).
In the "Xal" structure (which has several other names), we can use `stdc_first_leading_one` to determine the index in the index block, then zero out the leading one bit to determine the index in the bucket.
This structure would be more efficient if processors provided a `log2mask` instruction which computes both the MSB and the remainder after masking the MSB in one instruction. (Similar to how `divmod` instructions work where the quotient and remainder are both computed in one instruction).
---
[1]: https://en.wikipedia.org/wiki/Hashed_array_tree
[2]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
reply