Here is another, interactive explanation of this phenomenon in IRV, as well as some alternatives that do not suffer this issue: https://ncase.me/ballot/
Does this mean that US automakers might start making light trucks again? I thought that the reason why they aren't made much any more was due to milage standards, but that wouldn't be an issue for electric trucks.
> I thought that the reason why they aren't made much any more was due to milage standards, but that wouldn't be an issue for electric trucks.
I'm guessing we will see something like CAFE standards for EVs when they become a majority of the market. Maybe they'll call it CAKE (Corporate Average Kilowatt-hour Economy). The same people now complaining about carbon emissions from ICE trucks will in the future complain about the appalling electricity consumption of electric trucks.
I really don't see the climate activist people saying "our work here is done, let's pack up and go home!" when the last ICE vehicle rolls off the assembly line. The battle lines will just shift and the Cybertruck/F150 Lightning/Hummer EV/Rivian R1T will become as reviled as their internal combustion counterparts are today.
I'm wondering, what entity enforces a uniqueness constraint on the URLs? Presumably it wouldn't be hard to copy the content & host & create a whole new URL, but what prevents you from just minting using the original URL?
I am a highlight reader. Going through this thread, I thought it would be nice to automate it, as it's a triple-click to highlight a paragraph in safari.
What if instead, it was just on hover? I'd like to opt into this for just pages with long text, and so I created a bookmarklet.
It works ok, if any fellow highlight readers want to give it a try, but does anyone with any sort of css-fu know how to make it more robust? I tried adding other tag:hovers, but nesting quickly makes this weird. Is there a way to select parents of text nodes?
If you expect the first round winner to always win, then what would be the point of doing RCV at all? First round RCV winner is the same as FPTP winner. The entire reason why you would pick RCV over FPTP is because of those cases where first round plurality winner doesn't express the intent of the electorate.
That said, the OP link goes into detail about real issues with RCV & describes superior alternatives.
Watching that video, there's not much in there that you couldn't do with vscode vim plugin. Lots of it was just setting up vim plugins to replicate behavior present in vscode itself. In vscode, these features can also usually (always?) be accessed via the keyboard.
As for mouse-reaching, just flip it over (maybe put a sticky note over laptop trackpads). If you touch it, think, hey, there's probably a way to do this without the mouse. For vim usage, I would also say the same thing about arrow keys (especially in insert mode). Disable these training wheels & see your productivity skyrocket.
I once printed this out & gave it to a pair of repeat Jehovah's Witness door-knockers I had befriended. Don't know how they took it as the next time they came around my roommates, unaware of our friendship, told them I moved & they never returned.
It is indeed in The Tao Is Silent — Raymond's first popular book and one of his best. There's a recent reading of the dialogue on YouTube by Curt Jaimungal, on the "Theory of Everything" channel: https://youtu.be/P-jh6tRh3Jw
Thanks! I had originally found it in Douglas Hofstadter's & Daniel Dennett's anthology, The Mind's I, which I also strongly recommend to those who haven't heard of it.
It's not just being held responsible for one's spouse's opinions (much less actions)— at least one of his own past judicial decisions now seems quite questionable in light of this:
The classic use of XOR-swap was to traverse a tree without needing a stack. As you traverse the tree, the forward links are swapped with backward links, so you can find your way back. Used in the mark phase of some early garbage collectors.
Yah, or just store both the forward and backwards links in a single variable by xoring the forward and backward links together and storing it. Then the list traversal direction is picked by selecting either the head or tail and starting the operation. Halves the cost of a doubly linked list, while allowing the same function to be used for forward and backwards traversal.
Halves the cost provided that touching that many cache lines is free. Even after you rewrite them back to how they were, the cache doesn't know, so has to write back every line.
If it's a balanced tree, you need only log(n) stack entries you can statically provision, and then other threads can traverse the tree at the same time.
Most of the traditional optimizations turned into pessimizations decades back. That has been a good thing.
> Even after you rewrite them back to how they were
Why would you do that? I was under the impression that the trick with the "XOR-ly linked list" is to keep these in RAM strictly in the XOR'd form. What exactly did you mean by "has to write back every line"?
If you're interested in this sort of thing "The Art of Garbage Collection" is the standard go-to text these days.
It's been a little while, but as I remember, the main reason for pointer reversing is to be able to not use any extra space to keep track of the list of grey (currently being processed) objects in a standard three-color collector. As you'll recall, a basic tracing collector marks each object as one of 3 colors: black, white, and grey. It must maintain the invariant that black objects never have pointers to white objects. A (full) GC cycle begins with all objects marked white, then the GC roots are marked grey. Then the collector repeatedly removes an object from the grey set, marks all of the white objects it points to as grey, and then marks the just removed grey object black. The GC cycle ends when there are no more grey objects, at which point all white objects are garbage and can be reclaimed.
This is often implemented by using a single bit in the object header to keep track of white/black, and a stack to keep track of the set of grey objects. In this setup, a white object is marked grey by setting the color bit in the object header to whichever color indicates black, and putting it in the grey set. That is, grey objects are really marked black, but in the grey set. In other words, the color bit in the object header is really a "white"/"not white" bit. This is the easiest way to ensure a white object never gets added twice to the grey set without having to explicitly mark the object as grey. (Some systems actually invert the sense of the color bit in the object header between major GC collections. In one major collection 0 means white, and the next major collection 0 means black. This avoids having to scan the heap marking all objects white at the beginning of the GC cycle.)
One way to implement the logical stack of grey objects is to use a singly-linked list. If you want to implement a linked list of objects without adding an extra pointer to every object's header, and you don't want to allocate any extra space in the middle of a garbage collection, then you need to figure out some kind of clever hack to re-purpose some existing space. I forget the exact details, but (1) if an object doesn't have any pointers in it, you can immediately mark it black without first adding it to the grey set ... and that's where I lose track of the details about how you keep track of which object pointer you've borrowed to reverse in order to use a linked list to implement your grey object stack.
So, I'm missing the key detail that makes the whole trick work, but at a high level, you have extra storage space of one pointer to point at the top of the grey stack. The object at the bottom of the grey stack has its pointer nulled out, and off to the side you keep track of that last final pointer to restore when you empty the grey stack (which ends the GC cycle). When you pop an object off of the grey stack, you point its pointer to the previous object popped off of the grey stack (thus restoring (re-reversing) its reversed pointer).
However, I can't for the life of me remember how you keep track of which pointer you've reversed in each object without using any extra space. I don't think you can always just use the first pointer in an object, because that could trap you in a cyclic sub-graph.
EDIT: I've found a few different sets of very vague lecture notes online that are super vague... just saying you reverse pointers in order to make a linked list of grey objects. However, if you reverse all of the pointers, you don't get a linked list, but a general graph. You need to have exactly one pointer per object in order to have a singly linked list. If you have some rule of always using the first (or last) non-null pointer in an object, you might still wind up in a situation where you're reversing a cycle of pointers. I found a nice slide deck showing the steps, but the example was acyclic, and there was no explanatory text.
I thought maybe there's a trick with using two bits for color in the object header, and using that to mark which pointer has been reversed by also marking the target object, but that breaks if there are multiple pointers to the specially marked object.
Maybe the unmentioned trick is to use tagged pointers to keep track of the one pointer in each grey object that has been reversed. I really hope that's not it. That just feels... less brilliant.
Aha... it seems I've been lied to! It seems the proof of correctness is for a binary graph (each node has an out-degree of at most 2, but cycles are allowed in the graph) and needs 2 extra bits of state per node. [0][1]
Now, one can represent any higher-degree graph as a binary graph by simply replacing any higher-degree nodes with a binary tree with the required number of out-nodes, but then that increases the number of extra bits required.
Gries's 2006 less formal writeup [1] is simple to extend to higher-degree nodes. Instead of his 2-bit counter, one can use a counter that goes from 0 to the number of out-links. My guess is that real implementations use tagged pointers to indicate which pointer has been reversed instead of using a counter in Gries's write-up.
I feel so lied to! No wonder I couldn't figure out how to do it without tagged pointers! Though, please correct me if you find a pointer reversal algorithm that doesn't use tagged pointers and is guaranteed to terminate in the case of arbitrary graph cycles.
That's not quite what I'm talking about. If you look at Gries's 2006 paper (the less formal one, not his formal proof of the algorithm), each node has 2 bits for state and two child pointers.
State 0: Node is white
State 1: Node is grey and child[0] points to parent
State 2: Node is grey and child[1] points to parent
State 3: Node is black and both child pointers are restored
To generalize this algorithm to nodes with k children, you need to either pack ceil(log2(k+1)) bits into object header and tag bits in the first few fields of the object, or else have a white/not-white bit in the object header and have one tag bit in each object field, indicating which pointer has been reversed to point to the parent node. The latter is less complex, but results in O(k^2) time complexity in the repeated scanning of the object to find the currently reversed pointer each time you recurse back up to the node while traversing the graph. To really maximize speed, I suspect the O(k^2) algorithm is used in practice for small k, and the more complex counter spread across tag bits of multiple pointers is used for nodes with larger k.
By any chance, were you referring instead to Richard Jones' "The Garbage Collection Handbook: The Art of Automatic Memory Management"?
Garbage Collection interests me greatly, and I was looking forward to exploring a new reference - as it turned out, I couldn't find anything titled "The Art of Garbage Collection", so I thought I'd ask.
