Brutkey

Per Vognsen
@pervognsen@mastodon.social

ASCII characters are not pixels: a deep dive into ASCII rendering. https://alexharri.com/blog/ascii-rendering

Per Vognsen
@pervognsen@mastodon.social

@fanf@mendeddrum.org Stained glass is a wonderful way of visualizing the overlap.

Per Vognsen
@pervognsen@mastodon.social

@fanf@mendeddrum.org This is good too.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange Correct. And remember what I said about the flexibility this opens up? You have to log the updates incrementally as they happen, but because you're not required to preserve the granularity except at bookmarks you can do things like coalesce or dedup changes since the last snapshot into an entirely different representation when someone takes a snapshot, if you'd like.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange As a silly example, suppose there's a snapshot where all the logged changes were writes to the same byte location. The only thing you ultimately have to care about for the snapshot is the initial value of the overwritten byte from the last snapshot, so everything else can be tossed. It's more or less log compaction but you don't have to use the same representation for the most recent op log and the snapshot log, if that makes sense.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange An easy way to implement any data structure like this is to implement the memory itself semi-persistently. That is, you have a semi-persistent abstract data type which is called a memory. It implements read_uint16, write_uint32, copy_bytes, undo, redo, etc, and it keeps an undo/redo log of what it overwrites and at what offset so you can undo/redo it later.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange You also want a snapshot method that essentially gives you an undo/redo boundary. That way the internal representation and granularity of the undo/redo log doesn't have to be 1:1 with individual update operations, which gives you more flexibility.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange Persistent trees are way too much overhead compared to an undo log, though, if you can't make use of any of their other advantages.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange An easy way to implement any data structure like this is to implement the memory itself semi-persistently. That is, you have a semi-persistent abstract data type which is called a memory. It implements read_uint16, write_uint32, copy_bytes, undo, redo, etc, and it keeps an undo/redo log of what it overwrites and at what offset so you can undo/redo it later.

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange Well, they're a very general technique and you'd have to adapt it. I'm assuming you don't want a flat key-value array per node since you want to support nodes with large/unbounded fanout?

Per Vognsen
@pervognsen@mastodon.social

@blackeggs@infosec.exchange The point is that you're dealing with a general tree-like structure just to represent a single node in a persistence-friendly way, i.e. you're essentially composing multiple persistent data structures and you should probably express your code in that way, and for that part you need balanced or radix trees or something like that.

Per Vognsen
@pervognsen@mastodon.social

@pkhuong@discuss.systems Hey Paul (or anyone else), what's the standard CS name for the (stable, non-reallocating) dynamic array data structure based on power-of-two segment lengths where you do two-level indexing via x = ilog2(i), y = i - (1 << x) where i is a 1-based linear index? I've always called it an exponentially segmented array but never been able to find the earliest reference in the literature or what the canonical name for it is; it feels basic enough that it should be in Knuth.