pervognsen

// The two sweetspots are 8-bit and 4-bit tags. In the latter case you can fit 14 32-bit keys in
// a cacheline-sized bucket and still have one leftover byte for metadata.

// As for how to choose tags for particular problems, Google's Swiss table and Facebook's F14 table
// both use hash bits that weren't used for the bucket indexing. This is ideal from an entropy perspective
// but it can be better to use some particular feature of the key that you'd otherwise check against anyway.
// For example, for 32-bit keys (with a usable sentinel value) you could use the 8 low bits as the tag
// while storing the remaining 24 bits in the rest of the bucket; that fits 16 keys per bucket. Or if the keys
// are strings you could store the length as the discriminator: with an 8-bit tag, 0 means an empty slot,
// 1..254 means a string of that length, and 255 means a string of length 255 or longer. With a 4-bit tag

pervognsen

// This is another take on the mark-compact collector from https://gist.github.com/pervognsen/7fe51bef8977cb249ac4c6f830f818a5
// To avoid having to do global compaction, our object indices will have two parts: a block index and a block offset.
// Within a block we have the same linear older-to-newer ordering by offset. But now blocks are allowed to have different ages.
// The block ages are defined by their position in a linked list: There's oldest_block and newest_block indices and then
// previous_block[block_index] for each block. This enables newest-to-oldest block iteration and the linked-list structure
// means that we can free an empty block by unlinking it. When a block is reused, it becomes the newest_block. Now, instead
// of only compacting within a block we will actually be coalescing across an age range of blocks. By doing so, we will usually
// be able to empty out entire blocks from the newer part of that age range, so they can be reused. This should have very similar
// performance characteri

gingerBill

package test

import "core:os"
import "core:fmt"
import "core:sync"
import "core:time"
import "core:thread"
import "core:text/scanner"
import "core:strings"

pervognsen

# 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

gingerBill

/*

Production  = production_name "=" [ Expression ] "." .
Expression  = Alternative { "|" Alternative } .
Alternative = Term { Term } .
Term        = production_name | token [ "…" token ] | Group | Option | Repetition .
Group       = "(" Expression ")" .
Option      = "[" Expression "]" .
Repetition  = "{" Expression "}" .

rygorous

---- On Ryzen 3950X

SimpleProf         :seconds  calls     count :     clk/call    clk/count
search_one         : 0.3081      1   8388480 : 1078358365.0       128.55
search_one_pf      : 0.3415      1   8388480 : 1195232920.0       142.49  <-- speculative prefetching (next options for L and R)
search_multi2      : 0.3062      1   8388480 : 1071663705.0       127.75
search_multi4      : 0.2454      1   8388480 :  859008465.0       102.40
search_multi8      : 0.2113      1   8388480 :  739533515.0        88.16
search_multi16     : 0.1996      1   8388480 :  698443550.0        83.26
search_multi32     : 0.1785      1   8388480 :  624785840.0        74.48

rygorous

<!DOCTYPE html>
<html>
<head>
  <title>Some fun HTML5 stuff</title>
<body>
  <p>All of this is valid syntax!
  <ul>
  <li>Don't need to close paragraphs (that one's old)
  <li>or list items
  <li>since it's clear from context!

Deanout

Commands from http://howtoforge.com/tutorial/ubuntu-ruby-on-rails
Yarn from https://linuxize.com/post/how-to-install-yarn-on-ubuntu-18-04/

gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3 \
7D2BAF1CF37B13E2069D6956105BD0E739499BDB

curl -sSL https://get.rvm.io | bash -s stable --ruby

Restart terminal

rygorous

// ---- triangle rasterizer

#define SUBPIXEL_SHIFT  8
#define SUBPIXEL_SCALE  (1 << SUBPIXEL_SHIFT)

static RADINLINE S64 det2x2(S32 a, S32 b, S32 c, S32 d)
{
   S64 r = (S64) a*d - (S64) b*c;
   return r >> SUBPIXEL_SHIFT;
}

oskarnp

import "core:fmt"
import "core:strings"

main :: proc() {
	// Demo: Split `text` on any character in delimiter string.
	{
		text := "\nThis is a long text\nwith line breaks.";
		lines_itr := split_iterator(text, "\n");
		for line in split_any_next(&lines_itr) {
			fmt.println(string(line));