Skip to content

Instantly share code, notes, and snippets.

Per Vognsen pervognsen

Block or report user

Report or block pervognsen

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
View tail_recursion_to_iteration.c
// Version 1: Recursion.
node_t *find1(node_t *node, int key) {
if (!node) {
return NULL;
}
if (key < node->key) {
return find1(node->left, key);
} else if (key == node->key) {
return node;
View flame_cholesky.py
def blocks(A, block_size=(1, 1)):
i, j = block_size
while len(A):
yield A[:i, :j], A[:i, j:], A[i:, :j], A[i:, j:]
A = A[i:, j:]
# 2400 ms for 1000x1000 matrix (~0.4 GFLOPS/sec). Equivalent C code is only twice as fast (~0.8 GFLOPS/sec).
# The reason the C code isn't much faster is that it's an O(n^3) algorithm and most of the time is spent in
# the O(n^2) kernel routine for the outer product in A11[:] -= np.outer(A10, A10). Even if we posit that Python
# is 1000x slower than C for the outer loop, that's still 1000n + n^3 vs n^3, which is negligible for n = 1000.
View cholesky_update.py
def givens(x, y):
r = np.hypot(x, y)
if np.isclose(r, 0):
return x, 1, 0
return r, x / r, y / r
def cholesky_update(L, x):
m, n = A.shape
x = x.copy()
for i in range(m):
View bit_algebra.md

Here's an example of an algebraic approach to bitwise operations. I'm intentionally choosing something that is obvious from the programmer's point of view to see what it corresponds to algebraically.

We know that bitwise rotation of an n-bit word x can be done with left/shift shifts:

(x << 1) | (x >> (n-1)) = (x << 1) ^ (x >> (n-1)).

Algebraically, this means that the rotation operator C satisfies C = L + R^(n-1). Since C is a rotation it must satisfy C^n = 1, i.e. if we rotate n times we should end up where we started. This corresponds to the identity (L + R^(n-1))^n = 1.

View input_bindings.md

Every emulator should have most of these input-related features but I haven't found anything with more than a small fraction:

Default and custom input profiles. Custom profiles can have game-specific input bindings. Bindings in custom profiles set to the 'default' value defer to the binding in the default profile; it's important that custom profiles aren't just initialized as a copy of the then-current default profile as this makes it impossible to later change some non-overridden binding in the default profile and have it automatically propagate to existing custom profiles.

The emulator should remember which custom profile was last used for which game, based on the ROM hash or filename. (The emulator should also automatically save any relevant per-game emulator settings, but I think you want that separate from input profiles. As an example of what not to do, if I set the CPU overclocking for Metal Slug in MAME to 200% to

View segarray.ion
typedef T = int;
var segs: T**;
var seg: T*;
var segcap = 1;
var segidx = 1;
func grow() {
seg = 0;
asetcap(seg, segcap);
apush(segs, seg);
View dispose.ion
struct File {
base: Disposable;
libc_file: libc.FILE*;
}
func file_dispose(data: void*) {
self: File* = data;
if (self.libc_file) {
libc.fclose(self.libc_file);
}
View type_normalization.ion
func normalize_func(type: Type*): Type* {
key: char[];
num_params := alen(type.tfunc.params);
for (i := 0; i < num_params; i++) {
param := normalize(type.tfunc.params[i]);
acatn(key, (:char*)param, sizeof(param));
}
ret := normalize(type.tfunc.ret);
acatn(key, (:char*)ret, sizeof(ret));
normalized := agetn(normalized_funcs, key, alen(key));
View compiletime.md

We were having a discussion about compilation and linking performance on Twitter and I decided to do some measurements of the current Ion compiler, which is written in C. It's built via a main.c file that #includes everything else. The codebase contained 8,840 lines of code when I measured this. It only has a handful of external includes for the C standard library.

Here I'm doing a full rebuild with fast-debug flags, using the /Bt flag to give a timing breakdown between frontend, backend and link:

OptRef: Total time = 0.000s
OptIcf: Total time = 0.015s
Pass 1: Interval #1, time = 0.062s
Pass 2: Interval #2, time = 0.016s
View dispose.ion
typedef DisposeFunc = func(void*);
typedef DisposeMark = usize;
struct Disposable {
dispose: DisposeFunc;
mark: DisposeMark;
}
@threadlocal
var disposables: Disposable*[];
You can’t perform that action at this time.