psykotic
As a self-taught who later went to university for pure mathematics (which I got interested in through game programming), that was not my experience with the late 90s, early 2000s generation of self-taught game programmers. I think you have to go back 5 to 10 years earlier for that stereotype to have merit; the transition from 2D to 3D filtered out some people.
In the post-Quake generation, the sexy thing for budding game programmers was 3D graphics programming. For the most part you had no choice [1] but to read, understand and implement SIGRAPH papers and doctoral dissertations to learn the ropes, which in turn forced us to learn a lot of the formal prerequisites albeit unevenly. And there were a lot of advanced data structures involved with visibility determination (and later level of detail), which was the focal point of graphics in the Quake 1 and 2 era before it fell to the wayside once the dominance of GPUs made more brute-force approaches the right choice. So whether you liked it or not, you had to master a decent swath of university-level CS and math.
The main thing self-taughts generally lacked when joining the industry were the same thing all new employees lacked: they don't yet know how to work in teams, they don't know how to manage time, scope and complexity (though it helps if you've worked on larger personal projects of your own), they cannot make long-term engineering trade-offs (reliability, cost of making changes early vs late, flexibility vs performance, etc) because they haven't gone through full project cycles, and so on.
[1] There were a few useful resources like Abrash's Dr. Dobbs articles on Quake which were partially pre-digested for easier consumption by programmers, but it was still daunting if you didn't understand the math. And the rate of progress was so high in this period that the few reliable sources of how-to information were so quickly out of date that you _had_ to keep up with the academic research and experiment by implementing and improving it yourself.
Mara is right. ARMv8 supports relaxed memory ordering but its memory model does not support acquire-release ordering without sequential consistency. It's not a case of one ISA's memory model being strictly superior to the other. Relaxed memory ordering is not supported by x86. Therefore ARMv8 is superior in that respect.
I'll quote some relevant excerpts from B2.3.11:
Arm provides a set of instructions with Acquire semantics for loads, and Release semantics for stores. These instructions support the Release Consistency sequentially consistent (RCsc) model.
Where a Load-Acquire appears in program order after a Store-Release, the memory access generated by the Store-Release instruction is Observed-by each PE to the extent that PE is required to observe the access coherently, before the memory access generated by the Load-Acquire instruction is Observed-by that PE, to the extent that the PE is required to observe the access coherently.
// Thread 1
flag1.store(1, SeqCst)
if flag2.load(SeqCst) == 0 {
// Guarded action
}
// Thread 2
flag2.store(1, SeqCst)
if flag1.load(SeqCst) == 0 {
// Guarded action
}
The second excerpt from the Architecture Reference Manual says that if you use their load-acquire (ldarb) and store-release (stlrb) instructions, it is not possible for the store-release to be moved after the load-acquire, as observed by PEs (processing elements, their abstraction of hardware threads).
If you're still not convinced, let's look at how C++ compilers implement acquire-release vs sequential consistency on x86 and ARMv8:
https://godbolt.org/z/3fd5jse18
As you can see for yourself, the machine code on ARMv8 is identical for thread_acq_rel and thread_seq_cst. Whereas on x86 the thread_seq_cst code has to use xchg (an alternative to store + mfence) to achieve sequential consistency.
The fact that
f(g(x))
{ let y = g(x); f(y) }
> Personally I really like the spot readability of explicit types.
You can use an IDE that displays inferred types as type inlays (for variables) and as sidebar info (for expressions). But I've often wanted a way to export such sideband data (including subexpression types and cross-reference links) so you could display it for code reviews, etc, without teaching those tools about your language specifically, so I'm sympathetic to the general goal.
Regarding explicitness and readability, I like Rust's idea of letting you partially specify types by using _ as a placeholder to say "infer this part". For example, you can specify that something is a Vec without specifying its item type:
let v: Vec<_> = iter.collect();I'm curious what obstacle you have in mind for "multiple numbers".
The problem is equivalent to a distance query on a data structure, i.e. enumerate everything within a distance tol of a query point x in an appropriate distance metric. There are many data structures for this problem (it's a basic building block in computational geometry). But I assume the hashing solution you have in mind is what we usually call a hash grid in gamedev and graphics, which works well when tol is fixed for the lifetime of the data structure. [1] Namely, you define a grid with cell size tol and map a point x to the index cell(x) of its containing cell, which is just a rounding operation. Then you can use a hash table keyed by cell(x) to store the contents of an unbounded, sparse grid. To perform a distance query from x you need to check not just x's cell but some of the immediately neighboring cells and then filter all of those candidates based on the pairwise distance. [2] [3]
This approach works with any distance metric (including the usual suspects L^2, L^1 and L^inf) and in any dimension d although the worst-case number of cells to check in the hash is 2^d, so the curse of dimensionality is present and in high-dimensional spaces another data structure not based on rectilinear partitioning would be preferable. But hashing does work with "multiple numbers" if by "multiple numbers" you mean a vector (with not too many components) where tolerance is defined by a distance metric.
[1] Actually, hash grids work well any time the query radius is on roughly the same scale as the cell size. But if the query radius is a lot smaller than the cell size then the grid is too coarse to perform adequate pre-filtering. And if the query radius is larger than the cell size you have to check a bigger neighborhood of cells (i.e. more hash lookups) to enumerate all the candidates.
[2] Depending on the read vs write ratio, you can actually flip this around by storing each point in multiple cells so that queries only need one hash table lookup at the expense of slightly less precise pre-filtering.
[3] Instead of doing multiple hash table lookups, you can also have each occupied cell store pointers to neighboring cells (null for unoccupied neighbors), which replaces hash table lookups for the neighbors with plain memory loads. A variation on this trick is to instead store bit flags to avoid doing hash table lookups for neighboring cells which are known to be empty; this takes up far less memory.
That said, your thesis about the relative difficulty of doing this for C++ vs Java seems hard to argue against, and the rapid, continuous growth in C++'s surface area and complexity since C++11 surely hasn't helped.
Yes, and it took a surprisingly long time before anyone bothered to do the theoretical analysis. Some good papers to check out if anyone is interested are Deletion Without Rebalancing in Multiway Search Trees (http://sidsen.azurewebsites.net/papers/relaxed-b-tree-tods.p...) and Deletion Without Rebalancing in Binary Search Trees (http://sidsen.azurewebsites.net//papers/ravl-trees-journal.p...). Jeff Erickson also has some good notes on using local and global rebuilds for search trees: https://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-s...
It's intuitively clear that worst-case performance [1] can degrade to a function of the number of insertions since a rebuild (as opposed to the number of currently live items) when you use relaxed deletion. If you can afford to globally rebuild the tree you get to play the usual amortization tricks, but global rebuilds can be problematic in a large-scale live database; one solution is to rebuild from a snapshot in the background (on another thread or machine) and then replay late arriving operations before switching over to the rebuilt tree. But if someone is okay with the amortization spikes from rehashing a hash table, they should be okay with non-incremental global rebuilds for search trees; a hash table where deletions leave behind tombstones and the table is rehashed when the ratio of tombstones gets too high is basically the same idea.
[1] Ideally before most shared libraries have been loaded. I should do a simulation to get some quantitative estimates, but my hunch is that ASLR hurts badly even if each loaded library only takes up one 4 kB page. E.g. if you have an empty address space, allocate a 4 kB page at a random address and split the space in two around it, then try to densely pack as many 8 GB ranges in there as possible, you lose one potential 8 GB range (even if the ranges only require 4 kB alignment for their base address). Whenever such splits don't land in the same 8 GB clump, you lose a potential 8 GB range per split.
With 8-byte keys and the usual 64-byte cache line size, you end up with 8 keys per interior node's key array. That's a pretty bad range for the "simple linear search" most people would write, which is going to be dominated by the expected branch mispredict cost. The idea of using a hint to guess a starting position for either linear or binary search has the same issue. You need branches to capitalize on the best case vs worst case spread, and the mispredict cost will dominate for smaller arrays like this.
If you care about speed for this case, use a fast branchless binary search or a vectorized linear search (the latter will have an edge). An additional minor consideration for B-tree traversal is the latency of vector vs scalar loads since you don't know the load address (except for the root node) until you've finished searching the parent node's key array. That is not necessarily true for vectorized searches of small arrays in general, where the vector load addresses may be key independent (like the B-tree root node is here) and so in that case the few extra cycles of L1 load-to-use latency for vector loads (and higher load latencies in general) can often be hidden.
[1] By B-tree I am referring to in-memory B+ trees. A disk-based B+ tree would usually be built around page-granularity nodes. In that regime a branchless binary search for integer/float keys (with software prefetch to populate the cache ahead of the data dependency chains) that finishes off with a vectorized linear search is likely going to be the winner. The B-tree slack interval (M/2, M] helps since it guarantees a fully unrolled binary search with lg(M) steps won't waste any steps. You can still support "underflowing" B-tree nodes with the same branchless code path.
Anyway, invariant RDTSC's tick rate is completely separate from the core clock. So the main issue you have to worry about with invariant RDTSC is having your process unscheduled or having ticks "stolen" by interrupts (which includes firmware invisible to the kernel or hypervisor).
If you start with a word in a GPR and want to compute its popcount into another GPR, you need to move the GPR into a vector register, do the CNT, do the horizontal sum, and move the result back into a GPR.
It's been a while since I did the test, but I think the latency I measured on the Apple M1 perf cores (Firestorm) for that instruction sequence was around 15 cycles. [1] Compare that to POPCNT being 3 cycles on Intel and it really hurts for latency-sensitive uses of word popcount. However, CNT is great for doing large reductions since you can do 32 rounds of CNT + vector add before the bytewise counters can overflow, so you can amortize away the cost of the horizontal reduction. (People end up doing similar things on x86 for large streaming popcount calculations.)
A lot of my micro-optimized code relies on low-latency word popcount, so I selfishly want every processor to have an Intel-style popcount. :)
[1] You can actually beat the latency of that very easily with an L1-resident byte popcount lookup table + sum reduction. This table is only 256B, so it's very practical. You can shave off 1-2 cycles of latency by going to a halfword popcount lookup table, which is 64KB. That kind of cache hogging will perform better in microbenchmarks than in real applications but with the M1's large L1 cache of 128KB per core it might be a net win if you have a tight loop that's heavily affected by popcount latency.
For something like B-trees you want to make a distinction between internal and external references. Internal references ("child pointers") can just be 32-bit indices into an array of fixed-size items (each the size of a cache line or a multiple thereof) or even naked pointers if you don't mind the inefficiency on 64-bit platforms. Depending on the requirements, external references are often best represented as some kind of handle with explicit registration. This is especially helpful if you need to manage the lifetime for persistent B-trees (where different trees can share subtrees) since the external reference handles serve as GC roots, so you require them to be explicitly registered while the internal references are owned by the B-tree heap and can therefore be direct while still being traceable or refcountable; this also works well for dealing with reclamation in a concurrent system.
So, you almost always want to distinguish internal vs external references, and handles are primarily a solution candidate for external references.
The chordal interference graphs that arise from (not necessarily structured) programs in SSA form are optimally colorable in linear time. That approach is a solid basis for a register allocator but it's worth noting that it's not solving the same problem because the introduced phi nodes split the original live ranges at CFG join points, so you're not coloring the same interference graph the program had prior to SSA conversion. In practice a good register allocator already needs to have well-tuned heuristics for spill/fill/split/coalesce placement regardless of whether it uses SSA-based coloring, so the extra splits introduced by the SSA conversion are optimized as part of that process.
In the special case where your SSA program is structured and the code is presented to the backend in its natural order, the perfect elimination order for the chordal interference graph is just backward code order. As a result you can do optimal register coloring for such programs in a single backward pass (which can be integrated into a backward code generation pass if you're trying to go fast).
You have a separate tree for each power-of-two scale. The tree corresponding to scale k contains intervals with length between 2^k and 2^(k+1). An interval [u, v] is put in the tree corresponding to scale lg(v - u) under the key u. If you have a query window [a, b] you turn it into a range query a - 2^k <= u <= b for each relevant scale k and filter matches by interval overlap between [u, v] and [a, b]. "Each relevant scale" is defined by the desired level of detail, e.g. you don't query scales which are too small relative to the current zoom level.
Each scale actually has two trees. One type is what I just described. The other type is a summary tree which contains bounding intervals with recursive summaries of all intervals at finer scales. When you cut off queries at scale k you also include data from the summary tree at scale k so that all data in the query window is returned, either verbatim or as part of the bounding intervals with summaries.
An efficient, convenient way of implementing this is to stream the time series data to disk to separate append-only files for each scale. You can start doing interval queries immediately with a reasonable slowdown by directly doing binary search on the raw scale-segregated files (if the records are variable length you can use a COBS-style encoding so you can sync to the nearest record from a random point in the file). That said, the write amplification for a high-fanout B+ tree index is tiny here and building it in a streaming fashion is basically free, so generating the index synchronously is my recommendation. You can also generate the summary files in a streaming fashion but since they involve significant write amplification it's worth decoupling that task to a process with lower IO priority.
To implement the interval query for [a, b] at a given scale you use the B+ tree index to find the starting position in the append-only record file for that scale using the a - 2^k lower bound and just do a linear scan in the file until you exceed b.
There's a bunch of variations and optimizations (e.g. coarser scales than powers of two) but that's the gist of it.
// We need i + 15 < length to keep the last written entry in bounds.
for (; i < length - 15; i += 15)As you noticed, the FizzBuzz pattern has a period of 15. So if you want to go fast, just go directly to a 15x vectorized unroll with unaligned stores.
Assuming 32-byte vectors like with AVX2, you initialize two vector registers v0, v1 to hold the pattern of 15 4-byte values (the 16th value doesn't matter) corresponding to 0 through 15. You also have corresponding delta vector registers d0, d1 whose entries are +15 for the "pass-through" values and 0 for the -1/-2/-3 sentinel values. The loop kernel is just this:
store_unaligned(p, v0)
store_unaligned(p + 8, v1)
v0 += d0
v1 += d1
p += 15
You could remove the unaligned stores with a monstrous lcm(15, 16) = 240x unroll (16 shifted instances of the above kernel) but you wouldn't be able to keep all the necessary loop state in registers.
The real hack is implicit IDs, not the ID stack (which is just a way of implementing a hierarchical namespace like file system paths or URLs). Implicit IDs just work 99% of the time and rarely require manual intervention, so seeking a 100% solution is a tempting siren song. But once you actually start writing UIs like this, the 99% solution is just fine.
[1] The prevailing use of hashing is a consequence of the popular immediate-mode UI libraries being focused on minimal state per widget. If you already plan to maintain significant state for every widget (as you would need in an immediate-mode interface to win32 controls) you would just do hierarchical interning with sequential id assignment (i.e. the first time a new subid is used with a given parent, it is assigned a sequential global id and put in a table so the association can be memoized across frames) and then hash collisions won't cause id collisions.