7 ms·
Back in 2024, I was trying to optimize PostgreSQL's NUMERIC data type, which is base-10000, using Karatsuba. The problem of finding the optimal threshold of wh
by JoelJacobson 2mo ago
Back in 2024, I was trying to optimize PostgreSQL's NUMERIC data type, which is base-10000, using Karatsuba. The problem of finding the optimal threshold of when to switch to Karatsuba turned out to be really hard, since it depends on the size of both factors combined. After some hundreds of hours, I gave up, and started thinking about if there could be a simpler solution. I came to think about another idea I'd had before but abandoned, about 64-bit modernizing the digit base from 10k to 100M, but that would be a challenge due to existing data on disk. Desperate of finding a solution, I wondered if it could be fast enough to do on-the-fly conversion back and forth between base-10k and base-100M, and then realized that, yes, of course, it will be fast already for quite small N (testing shows already between 3-6 base digits). The trick basically reduced the N in O(N^2) into half, i.e. O((N/2)^2), with some O(2*N) cost for the conversion back and forth.
I had a lot of fun hacking on this idea together with the maintainer of the NUMERIC data type, and after two months the patch finally was ready and got committed:
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=8dc28d7eb868b6ce5a51614628bf46fc63c7e90c https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...
- JoelJacobson 2mo agoHere is the full pgsql-hackers mailing list thread where you can follow our work from initial idea to commit: https://www.postgresql.org/message-id/flat/9d8a4a42-c354-41f3-bbf3-199e1957db97%40app.fastmail.com https://www.postgresql.org/message-id/flat/9d8a4a42-c354-41f...
- sureglymop 2mo agoLove this, thank you for providing the context!
- wormslayer666 2mo agoA bit tangential, but the folks behind the GNU Multiple Precision Library (GMPLib) have the problem of choosing algorithms more or less fleshed out. They've got some fairly approachable manual pages[1] for the various algorithms they use as operand sizes scale up, where Karatsuba is only the second of six options in terms of operational complexity. [1] https://gmplib.org/manual/Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms
- inigyou 2mo agoThis really demonstrates the utility of pulling in a library written by experts in the field the library handles.
- Bratmon 2mo agoThis is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?
- deleted 2mo ago[deleted]
- dspillett 2mo agoOr increasingly, a library written by an LLM referencing a pile of such “one guy” projects of varying levels of suck (from actually good to good-got-it-is-full-of-suck).
- spullara 2mo agoWhat I have been seeing recently is having a great LLM rewrite the library leads to fewer bugs and also optimized for your use case. More expensive for sure than pulling something like epub.js but when the library has infinite open issues it can be a lot better.
- layer8 2mo agoYou defer to the advice of experts you trust. Which somehow have become harder to come by in terms of signal to noise than 20-30 years ago.
- xtajv 2mo ago1. Read the code 2. Don't. Encapsulate and put yourself in a position to swap out the implementation at will. (Maybe you'll swap out an unnecessary dependency for a simple helper function of your own).
- kurlberg 2mo agoIt's complicated. :-) There is a nice picture of the "best" choice for different ranges of sizes of numbers to be multiplied at http://gmplib.org/devel/log.i7.1024.png http://gmplib.org/devel/log.i7.1024.png More context and explanation can be found at: http://gmplib.org/devel/ http://gmplib.org/devel/