Skip to content

Instantly share code, notes, and snippets.

@pervognsen
pervognsen / asdf.cpp
Last active March 24, 2024 06:22
symmetric iterator interface
#include <utility>
// ...
template<class L, class R>
struct ConcatIterator
{
L left;
R right;
@pervognsen
pervognsen / array.inl.h
Last active March 24, 2024 06:15
somewhat palatable templates in c
struct A {
int size;
int capacity;
T *data;
};
typedef struct A A;
void A_(Create)(A *array, int capacity);
void A_(Destroy)(A *array);
#include <deque>
#include <Windows.h>
HANDLE scheduler_thread;
PUMS_COMPLETION_LIST scheduler_completion_list;
HANDLE scheduler_completion_event;
HANDLE scheduler_initialized_event;
HANDLE scheduler_shutdown_event;
enum BlockReason {

Multi-dimensional array views for systems programmers

As C programmers, most of us think of pointer arithmetic for multi-dimensional arrays in a nested way:

The address for a 1-dimensional array is base + x. The address for a 2-dimensional array is base + x + y*x_size for row-major layout and base + y + x*y_size for column-major layout. The address for a 3-dimensional array is base + x + (y + z*y_size)*x_size for row-column-major layout. And so on.

struct Object {
Key key; // The key is any piece of data that uniquely identifies the object.
// ...
};
struct Handle {
Key key;
Index index; // This caches a speculative table index for an object with the corresponding key.
};
// x64 encoding
enum Reg {
RAX, RCX, RDX, RBX, RSP, RBP, RSI, RDI,
R8, R9, R10, R11, R12, R13, R14, R15,
};
enum XmmReg {
XMM0, XMM1, XMM2, XMM3, XMM4, XMM5, XMM6, XMM7,
XMM8, XMM9, XMM10, XMM11, XMM12, XMM13, XMM14, XMM15,
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef struct ion_type_t ion_type_t;
typedef struct ion_value_t ion_value_t;
typedef struct ion_state_t ion_state_t;
typedef struct ion_instruction_t ion_instruction_t;
typedef void (*ion_operation_t)(ion_state_t *, ion_value_t, ion_value_t, ion_value_t *);
// This can grow a Robin Hood linear probing hash table near word-at-a-time memcpy speeds. If you're confused why I use 'keys'
// to describe the hash values, it's because my favorite perspective on Robin Hood (which I learned from Paul Khuong)
// is that it's just a sorted gap array which is MSB bucketed and insertion sorted per chain:
// https://pvk.ca/Blog/2019/09/29/a-couple-of-probabilistic-worst-case-bounds-for-robin-hood-linear-probing/
// The more widely known "max displacement" picture of Robin Hood hashing also has strengths since the max displacement
// can be stored very compactly. You can see a micro-optimized example of that here for small tables where the max displacement
// can fit in 4 bits: Sub-nanosecond Searches Using Vector Instructions, https://www.youtube.com/watch?v=paxIkKBzqBU
void grow(Table *table) {
u64 exp = 64 - table->shift;
// We grow the table downward in place by a factor of 2 (not counting the overflow area at table->end).
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
const char *keywords[] = {
"completed_in",
"contributors",
"contributors_enabled",
"coordinates",
"count",
void gen_mul(Value *dest, Value *src) {
if (isconst(dest)) {
gen_swap(dest, src); // this doesn't generate instructions and just swaps descriptors ("value renaming")
}
val_to_reg(dest); // the post-condition is that dest is allocated to a register
if (isconst(src) && isimm32(src->ival)) {
if (src->ival == 0) {
int_to_val(dest, 0);
} else if (src->ival == 1) {
// do nothing