diff options
| -rw-r--r-- | docs/design/023-optimizing-tier.md | 7 | ||||
| -rw-r--r-- | research/experiments/040-against-c/2026-10-05-forms.jsonl | 1 | ||||
| -rw-r--r-- | research/experiments/040-against-c/forms.c | 92 |
3 files changed, 100 insertions, 0 deletions
diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md index 78a4591..6a4c23d 100644 --- a/docs/design/023-optimizing-tier.md +++ b/docs/design/023-optimizing-tier.md @@ -141,6 +141,13 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 - SSA의 선형 스캔 할당(정수, 실수 둘). 루프 깊이로 값의 무게를 정한다. 넘치면 프레임의 슬롯. - 022의 기계어 조각(태그 붙은 열 주소, 장부, 줄 밖 길, `pure_run_rest`)은 계층의 하위 단계로 쓴다. - 컴파일은 블록이 처음 돌 때 한다(지금처럼). 그 값은 재서 밝힌다. +- **잰 것: 행렬곱 안쪽 루프의 꼴**(`research/experiments/040-against-c/forms.c`, 2026-10-05, 11번의 중앙값). 계층이 낸 꼴 + (위치를 곱셈과 덧셈으로, 곱과 합을 2^53 아래로 검사, 적재마다 꽉 찬 리스트의 비트를 봄) 20.7 ms, 검사와 비트를 빼도 20.1, 각 열의 + 포인터를 보폭만큼 옮기면(곱하기-더하기 하나로 합) 13.1, 곱과 더하기를 나누면(합의 사슬이 더하기 하나) 10.0, 거기에 두 검사를 넣으면 + 10.2, 적재 앞에 비트를 보면 13.4. 위치의 곱셈이 2배, 곱하기-더하기의 사슬이 1.3배, 적재 앞의 분기가 1.34배이고, 오버플로 검사는 + 거의 공짜다. 그래서 순서는 **포인터 귀납 변수**(아핀 키의 칸 주소를 루프의 φ로) 다음에, 그래도 비트의 분기가 남으면 **꽉 찬 + 경우의 사본**(키로만 찾는 리스트가 모두 꽉 찬 DENSE일 때의 루프 본문을 하나 더 내고 루프를 열 때 고른다). 같은 배열을 정적으로 + 둔 C는 3.8 ms(바깥 루프를 벡터로 묶는다), `natural.h`의 C는 7.5. ### 6. 표현 (바닥이 가정한 것) diff --git a/research/experiments/040-against-c/2026-10-05-forms.jsonl b/research/experiments/040-against-c/2026-10-05-forms.jsonl new file mode 100644 index 0000000..8d7ad78 --- /dev/null +++ b/research/experiments/040-against-c/2026-10-05-forms.jsonl @@ -0,0 +1 @@ +{"index":20.69,"plain":20.11,"pointer":13.12,"apart":10.02,"checks":10.24,"bits":13.37,"c":3.76,"same":true} diff --git a/research/experiments/040-against-c/forms.c b/research/experiments/040-against-c/forms.c new file mode 100644 index 0000000..93c3e9b --- /dev/null +++ b/research/experiments/040-against-c/forms.c @@ -0,0 +1,92 @@ +/* matmul's inner loop (200 x 200 cells of u32) in the forms the tier may + * make it, as AArch64 assembly, against natural.h's C on the same Pi + * (research 124, docs/design/023 section 5): + * index the cell at column + (i * n + k) and column + (k * n + j), each + * found by a multiply and an add; the product and the sum each + * checked below 2^53; a full list's bit tested before each load + * (the tier's code at e4b4694) + * plain index, no checks, no bit tested, multiply-add into the sum + * pointer a pointer to each column stepped by its stride, multiply-add + * apart pointer, the multiply and the add apart (the sum's chain an add) + * checks apart, the product and the sum checked below 2^53 + * bits apart, a full list's bit tested before each load + * Each sums every product (the answers must be equal); the median of 11. */ +#define _POSIX_C_SOURCE 200809L +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +enum { N = 200 }; +static uint32_t A[N * N], B[N * N]; +static double DA[N * N], DB[N * N]; +static double now(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return t.tv_sec * 1e3 + t.tv_nsec / 1e6; +} +#define LOOP(name, body, ...) \ + static uint64_t name(void) { \ + uint64_t total = 0, flag = 1; \ + for (uint64_t i = 0; i < N; ++i) \ + for (uint64_t j = 0; j < N; ++j) { \ + uint64_t s = 0, k = 0, base = i * N; \ + const uint32_t *pa = A + i * N, *pb = B + j; \ + __asm__ volatile(body : [s] "+r"(s), [k] "+r"(k), [pa] "+r"(pa), [pb] "+r"(pb) \ + : [base] "r"(base), [a] "r"(A), [b] "r"(B), [n] "r"((uint64_t)N), [j] "r"(j), \ + [flag] "r"(flag) \ + : "x10", "x20", "x24", "x27", "cc", "memory"); \ + total += s; \ + } \ + return total; \ + } +LOOP(index, "1: add x20, %[base], %[k]\n tbz %w[flag], #0, 9f\n ldr w24, [%[a], x20, lsl #2]\n mul x20, %[k], %[n]\n" + " add x20, x20, %[j]\n tbz %w[flag], #0, 9f\n ldr w27, [%[b], x20, lsl #2]\n mul x20, x24, x27\n" + " lsr x10, x20, #53\n cbnz x10, 9f\n add %[s], %[s], x20\n lsr x10, %[s], #53\n cbnz x10, 9f\n" + " add %[k], %[k], #1\n cmp %[k], %[n]\n b.lo 1b\n 9:\n") +LOOP(plain, "1: add x20, %[base], %[k]\n ldr w24, [%[a], x20, lsl #2]\n mul x20, %[k], %[n]\n add x20, x20, %[j]\n" + " ldr w27, [%[b], x20, lsl #2]\n madd %[s], x24, x27, %[s]\n add %[k], %[k], #1\n cmp %[k], %[n]\n b.lo 1b\n") +LOOP(pointer, "1: ldr w24, [%[pa]], #4\n ldr w27, [%[pb]]\n add %[pb], %[pb], #800\n madd %[s], x24, x27, %[s]\n" + " add %[k], %[k], #1\n cmp %[k], %[n]\n b.lo 1b\n") +LOOP(apart, "1: ldr w24, [%[pa]], #4\n ldr w27, [%[pb]]\n add %[pb], %[pb], #800\n mul x20, x24, x27\n add %[s], %[s], x20\n" + " add %[k], %[k], #1\n cmp %[k], %[n]\n b.lo 1b\n") +LOOP(checks, "1: ldr w24, [%[pa]], #4\n ldr w27, [%[pb]]\n add %[pb], %[pb], #800\n mul x20, x24, x27\n lsr x10, x20, #53\n" + " cbnz x10, 9f\n add %[s], %[s], x20\n lsr x10, %[s], #53\n cbnz x10, 9f\n add %[k], %[k], #1\n" + " cmp %[k], %[n]\n b.lo 1b\n 9:\n") +LOOP(bits, "1: tbz %w[flag], #0, 9f\n ldr w24, [%[pa]], #4\n tbz %w[flag], #0, 9f\n ldr w27, [%[pb]]\n add %[pb], %[pb], #800\n" + " mul x20, x24, x27\n add %[s], %[s], x20\n add %[k], %[k], #1\n cmp %[k], %[n]\n b.lo 1b\n 9:\n") +static uint64_t c(void) { /* natural.h's c_matmul, its sum */ + double total = 0; + for (uint32_t i = 0; i < N; ++i) + for (uint32_t j = 0; j < N; ++j) { + double s = 0; + for (uint32_t k = 0; k < N; ++k) s += DA[i * N + k] * DB[k * N + j]; + total += s; + } + return (uint64_t)total; +} +static int by(const void *a, const void *b) { return (*(const double *)a > *(const double *)b) - (*(const double *)a < *(const double *)b); } +int main(void) { + uint64_t x = 1; + for (int i = 0; i < N * N; ++i) { + x = x * 48271 % 2147483647, A[i] = (uint32_t)(x % 100), DA[i] = A[i]; + x = x * 48271 % 2147483647, B[i] = (uint32_t)(x % 100), DB[i] = B[i]; + } + static uint64_t (*const loops[])(void) = {index, plain, pointer, apart, checks, bits, c}; + static const char *const names[] = {"index", "plain", "pointer", "apart", "checks", "bits", "c"}; + double ms[7][11]; + uint64_t answer[7]; + for (int r = 0; r < 11; ++r) + for (int l = 0; l < 7; ++l) { + double t = now(); + answer[l] = loops[l](); + ms[l][r] = now() - t; + } + printf("{"); + for (int l = 0; l < 7; ++l) { + qsort(ms[l], 11, sizeof(double), by); + printf("%s\"%s\":%.2f", l ? "," : "", names[l], ms[l][5]); + } + int same = 1; + for (int l = 1; l < 7; ++l) same = same && answer[l] == answer[0]; + printf(",\"same\":%s}\n", same ? "true" : "false"); +} |