mlochbaum

15 ms·

91.
by mlochbaum 3y ago
Worth pointing out that this can depend a lot more on fiddly details than you might expect. In particular, you're dealing with a small fixed width allowing the hash to be stored in the table instead of the key. The article emphasizes v
92.
by mlochbaum 3y ago
A solution used in the Linux kernel[0] is to use a struct with the packed attribute, which implies the fields aren't necessarily aligned. Simplifying, I think this macro should work the same in gcc and similar: apply to any pointer to
93.
by mlochbaum 3y ago
Of course the method with length-1 axes will look good if it's the only way to do broadcasting. I've hardly touched it (and never saw the NumPy code mentioned in the quote), but some people in the APL community have so I'm re
94.
by mlochbaum 3y ago
There was a little discussion about this just Monday in the array programming chat[0]. Not many people commented but it doesn't look like anyone was in favor. I think the concern is that while broadcasting 1s is an easy mechanism to un
95.
by mlochbaum 3y ago
But using +/÷≢ to mean average isn't like using AddReduceDivideTally, it's like +/÷≢. With substantial array programming experience I do read this as a single word and pronounce it "average"; why should the fac
96.
by mlochbaum 3y ago
I did this! Singeli is an Elixir-like compile-time language where types and variables are first-class values, on top of C-ish semantics that are meant to be more like "portable assembly". It's designed for high-performance co
97.
by mlochbaum 3y ago
Sure, I've run into this when I went to do some language implementation in Go (dumped at [0]; didn't keep up with it just because I didn't have much reason to do it in the first place). I'd prefer ADTs, but I just frowne
98.
by mlochbaum 3y ago
Maybe so. I guess you're talking about option types, although it's not obvious to me that these do any better given the requirement that errors are always explicitly shown in the code. So maybe your problem is with that requiremen
99.
by mlochbaum 3y ago
Well, Lisp is just as functional as ML-family languages like OCaml and F#. Haskell's typed/pure FP is a branch off of this. Surely between Pike, Griesemer, and Thompson someone had some ML experience, but this doesn't matter
100.
by mlochbaum 3y ago
Misremembered about Iosevka: I requested support for a few other BQN characters after noticing it already had the double-struck ones ( https://github.com/be5invis/Iosevka/issues/870 ). The other three were requ
101.
by mlochbaum 3y ago
I'm responsible for this character being supported in Iosevka, JetBrains Mono, 3270, and Cozette, looks like. For arguments I wanted to stick to mathematical convention like f(x) without looking like a regular variable. While the lower
102.
by mlochbaum 3y ago
I just want you to accurately represent the performance, which as I've noted is not a big change. If a 2x speedup is definitive, why are you so desperate to push the number higher? You give the speedup of vqsort over std::sort in ideal
103.
by mlochbaum 3y ago
Yes, only your "10x" and "5-10x" numbers are overstated. Which is to say, all the quantitative comparison you've shared here, or in the vqsort README (aside from the link to Lukas's measurements, which is linke
104.
by mlochbaum 3y ago
Apologies, I misread that section and thought the only difference between tables 1 and 2 was the array size! Thanks for correcting my impression here, that's good to know. And very sorry for the misrepresentation.
105.
by mlochbaum 3y ago
Oh, I didn't know that about multi-way merge (regrettably I haven't really wrapped my head around SIMD merging yet). Got a source for this? https://vldb.org/pvldb/vol8/p1274-inoue.pdf mentions it but it
106.
by mlochbaum 3y ago
Vector registers are great, but it's important to remember that random-access cache is also very powerful hardware, and can be better-suited to a lot of searching and sorting tasks. One task where, unlike sorting, I think vectors hav
107.
by mlochbaum 3y ago
Please, you are overstating your case in a way that distracts from the issues at hand. I do agree that Linus's opinions are irrelevant to a lot of computing, and that sorting must make some use of SIMD for the best performance, and tha
108.
by mlochbaum 3y ago
pdqsort paper: https://arxiv.org/abs/2106.05123 fluxsort compiles in C++ just fine. Pre-sorted data is just the simplest example of adaptivity. Partially-sorted input can't be tracked easily by the caller and I be
109.
by mlochbaum 3y ago
longsort appears in cosmopolitan libc, and possibly gets embedded in all the output executables? For most applications the requirements are much less restrictive. I'm working on sorting for interpreted programming languages; I see >
110.
by mlochbaum 3y ago
Second part of the article, starting at "I thought it'd be useful to share something that's actually portable and executable".
111.
by mlochbaum 3y ago
Just realized that obviously you don't need stability if you're using in-place quicksort, so the tiny-sort heapsort is a better recommendation. 304 bytes, although the scaling to large arrays is much worse because of the awful acc
112.
by mlochbaum 3y ago
Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at? The code size might not end up quite as good (also requires malloc), but a branchless merge sort is a contender for a fast an
113.
by mlochbaum 3y ago
It depends on the size of the structs. For struct pointers you're likely better off sorting keys and pointers simultaneously. It doesn't matter much until you get to large sizes (millions), but sorting indices and then selecting
114.
by mlochbaum 3y ago
This is a point that I'm kind of fuzzy on: is there a specific requirement to not change the algorithm too much based on type/comparison? Like if the user calls it on a 1-byte type with default comparison, the best way to do this
115.
by mlochbaum 3y ago
Well, I know what you mean but "completely different" is potentially misleading here. The current ipnsort is using bidirectional merges developed for quadsort (the merging part of fluxsort) and the fulcrum partition from crumsort,
116.
by mlochbaum 3y ago
I'm not talking about ipnsort, which I think is great. It makes good use of existing work and doesn't use AVX at all. So extending it with AVX-512 partition code would also be a good project!
117.
by mlochbaum 3y ago
Steps to build a fast, highly adaptive AVX-512 sorting algorithm in C: - Clone fluxsort ( https://github.com/scandum/fluxsort ) - Replace the partitioning code in flux_default_partition and flux_reverse_partition with th
118.
by mlochbaum 3y ago
No, as you can check with some of the weirder arithmetic functions: </ ⍬ ⍝ Empty list 0 </ ,5 5 </ 0 5 1 </ 5 0 0 It would be more consistent in some ways thou
119.
by mlochbaum 3y ago
Haven't heard of it, and I couldn't find the phrase "piecewise-linear interpolation search" online at all. Care to share? In particular, how are the pieces determined? The Google paper is "The Case for Learned Index
120.
by mlochbaum 3y ago
Is this something you've benchmarked? If you're looking at Unicode, note that with just over a million possible code points, this is at the smaller end of speedups shown in the paper, which really gets going around 10 million. I d

More ›