Skip to content

Instantly share code, notes, and snippets.

# Here's a probably-not-new data structure I discovered after implementing weight-balanced trees with
# amortized subtree rebuilds (e.g. http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-scapegoat-splay.pdf)
# and realizing it was silly to turn a subtree into a sorted array with an in-order traversal only as an
# aid in constructing a balanced subtree in linear time. Why not replace the subtree by the sorted array and
# use binary search when hitting that leaf array? Then you'd defer any splitting of the array until inserts and
# deletes hit that leaf array. Only in hindsight did I realize this is similar to the rope data structure for strings.
# Unlike ropes, it's a key-value search tree for arbitrary ordered keys.
#
# The main attraction of this data structure is its simplicity (on par with a standard weight-balanced tree) and that it
# coalesces subtrees into contiguous arrays, which reduces memory overhead and boosts the performance of in-order traversals
typedef struct {
// These fields are internal state and not considered part of the public interface.
Node *parent;
int next_index;
// This field is public and valid to read after a call to next that returns true.
Node *child;
} Iter;
Iter iter_children(Node *node) {
buffer = b'' # This is the partial line buffer.
while 1:
buffer += socket.recv(1024) # Read up to 1024 bytes and append it to the buffer.
lines = buffer.split(b'\n') # Split the buffer by newlines.
buffer = lines[-1] # The last piece is a partial line.
for line in lines[:-1]: # Every other piece is a complete line.
process(line)
#define MAXN 65536
#define MAXLG 17
char A[MAXN];
struct entry {
int nr[2], p;
} L[MAXN];
int P[MAXLG][MAXN], N, i, stp, cnt;
typedef enum {
CMD_INT = NODE_INT,
CMD_NEG = NODE_NEG,
CMD_NOT = NODE_NOT,
CMD_ADD = NODE_ADD,
CMD_SUB = NODE_SUB,
CMD_RET = 128,
CMD_SETREF,
CMD_GETREF,
} Cmd;
func bisect(begin: Node*, end: Node*): Node*
return nth(begin, end, len(begin, end) / 2)
func print_reverse(begin: Node*, end: Node*)
if begin == end
return
mid := bisect(begin, end)
if mid != end
print_reverse(next(mid), end)
print_node(mid)
IF
Heard([ANYONE], 251182)
THEN
RESPONSE #100
ReallyForceSpell(Player1, CLERIC_BLESS)
ReallyForceSpell(Player1, CLERIC_AID)
ReallyForceSpell(Player1, CLERIC_DEFENSIVE_HARMONY)
ReallyForceSpell(Player1, CLERIC_PROTECTION_FROM_EVIL_10_FOOT)
ReallyForceSpell(Myself, CLERIC_DRAW_UPON_HOLY_MIGHT)
ReallyForceSpell(Myself, CLERIC_HOLY_POWER)

Per,

Patching inline-caches is rare, so taking a lock & doing single-threaded updates is fine. No CAS needed for performance, nor is false-sharing an issue (this data is also code, so nearly always resides with other read-only code).

Patching typically covers a bunch of X86 ops, at least 2 but maybe 3 or 4, depending. If any of the updates to these words happens on partial instructions, a racing other CPU might see a partial update.

Patching covers a set of X86 instruction words, more than fits in an 8-byte CAS. 16-byte CAS's must be aligned properly.

Putting all this together, these constraints imply:

  • Updates are done via CAS covering whole instructions. No CAS spans a partial instruction.

Partial redundancy elimination (PRE) is an optimization where you eliminate computations that are redundant on some but not all control flow paths.

Example:

if (...) {
    // ...
    int a = x + y;
    // ...
} else {

// ...

; Math48 Floating Point Package
; Version 1.1 Revision 1
; by Anders Hejlsberg
; 2532 Bytes
;HOPTABEL
JP FPADD
JP FPSUB
JP FPMUL