5 ms·
Any performance benchmarks between a simple C implementation of matrix multiplication like explained in the article and K one? Story time: 2 years ago, right b
by unnouinceput 4y ago
Any performance benchmarks between a simple C implementation of matrix multiplication like explained in the article and K one?
Story time: 2 years ago, right before 1st lockdown, I landed a client. A data scientist who had already implemented an algorithm which dealt with matrices, implemented by a previous programmer he hired. Said implementation was in Python, no more than 10 line altogether, which performed well when matrix size where small, like 10x10. But the problem was, his real work need it to have matrices of size 10^6 x 10^6. Not only the Python implementation had to be ran on a beast of server with 4TB of memory, it also took 3 days to finish. And while the algorithm was small in size in Python, its explaining paper was 4 pages in total, which took me 1 week to understand. And then an entire month to implement in C. But in the end, when all was said and done, the run time when used with real data was only 20 minutes and consumed only 8 GB of memory, though it did required at least 16 virtual processors.
Hence my question, in the end performance is what it matters, not number of lines.
- mlochbaum 4y agoK timing, squaring a 100x100 matrix in ngn/k: a:100 0N#?10000 / 100x100 double matrix \t:1000 a(+/*)\:a / Total of 1k runs in ms 1514 Following C program outputs 272 when compiled and run with -O3 -march=native. #include <stdio.h> #include <time.h> size_t monoclock(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); return 1000000000*ts.tv_sec + ts.tv_nsec; } int main() { const size_t n = 100; double a[n][n], r[n][n]; size_t t = monoclock(); for (size_t iter=0; iter<1000; iter++) { for (size_t i=0; i<n; i++) { for (size_t j=0; j<n; j++) { double sum = 0; for (size_t k=0; k<n; k++) sum += a[i][k]*a[k][j]; r[i][j] = sum; } } } printf("%lld\n", (monoclock() - t)/1000000); } So K is slower, by a factor of 5 rather than the 200 you saw with Python. K appears to scale to larger matrices better than C: 8664 in K vs 2588 in C for 200x200, but I can't be bothered to sort out heap allocation for the C code to do larger sizes. I would certainly not say that your story supports the idea that performance is what matters. In the month you took to implement the C version, the Python solution could have run ten times over, and there are many computations that only ever need to be performed once. Besides, I bet you were glad to have working Python code to use as a reference!
- unnouinceput 4y agoNice benchmarking, thank you for your effort. Also the scientist was leading a team, so my program would've been used by at least 20 people, 10 times per day. That was why Python one was a no go for them from beginning.
- harshreality 4y agoCan you share the algorithm, or anything computationally equivalent, for people to try benchmarking different implementations?
- unnouinceput 4y agoThe one I wrote 2 years ago? That's intellectual property of said data scientist, not mine. Al I can say is that I parallelize it a lot, hence the entire month. From programming point of view is a mess and hard to follow its ~5k lines. Usually parallel programming is a mess, you should take a look at any parallelization CUDA code available on GitHub.
- harshreality 4y agoWas the original just regular python, or numpy? The C version wasn't GPU-targeted though from your description. I'm curious what other implementations would be capable of, for instance julia, maybe gpu-targeted.
- unnouinceput 4y agoWe discussed, since we already agreed on parallelization, if he wanted CUDA, since that would've been even faster. But after discussing with his team, he said no GPU dependent implementation and I started the work. He never shared why no GPU implementation and I didn't pressed the matter further since I was already knee deep in trying to understand the algorithm which was the bigger stone to crack at the time.
- 4y ago