orlp

25 ms·

391.
by orlp 4y ago
I like the name Algorithmic Induction, or Inductive Programming. Just like how in an (strongly) inductive proof you use facts from Fact(0)..Fact(n) to prove Fact(n+1), with inductive programming you're using results from Result(0)..Res
392.
by orlp 4y ago
Yes, but conversely if there's 10 simultaneous orders the probability is 1 - (4095/4096) * (4094/4096) * ... * (4087/4096) = 1.093% to have a collision with a code consisting of 3 hexadecimal characters.
393.
by orlp 4y ago
There is an irony joke to be made here.
394.
by orlp 4y ago
I knew I recognized that name, nice to see you here Thomas, I love XOR filters! In fact I was thinking about writing a blog post (series) about random linear coding, fountain codes, XOR filters and ribbon filters...
395.
The World's Smallest Hash Table(orlp.net)
8 points by orlp 4y ago|1 comments
396.
by orlp 4y ago
Strange Matter ( https://en.wikipedia.org/wiki/Strangelet ) is conjectured to convert regular matter into it upon contact.
397.
by orlp 4y ago
For once the URL is actually working!
398.
by orlp 4y ago
Furthermore it is a common (even logical) misbelief that chopping out the higher frequencies after a Fourier transform is filtering them out. Unfortunately this merely zeroes the exact frequencies used to define the bins but leaves a lot of
399.
by orlp 4y ago
Fair enough, I meant viral biowarfare.
400.
by orlp 4y ago
I think if anything COVID has shown us that biological warfare makes as much sense as nuclear: none. In our globally connected world it's mutually assured destruction, and that's without even the need for your enemy to maintain st
401.
by orlp 4y ago
I am not saying it does actually work this way, but there is no reason a bulk import needs to touch the WAL at all during import. As long as a lock was held the entire time during an import on the table, the import procedure can simply wr
402.
by orlp 4y ago
Ripgrep and fd-find are tools written in Rust replacing grep and find. They are in my experience orders of magnitude faster, with arguments I can actually remember.
403.
by orlp 4y ago
One interesting complication for a lot of photos is that the bandwidth of the green channel is twice as high as the red and blue channels due to the Bayer filter mosaic.
404.
by orlp 4y ago
Can someone explain to me how you can have geostationary orbit around the poles?
405.
by orlp 4y ago
"When you tear out a man’s tongue, you are not proving him a liar, you’re only telling the world that you fear what he might say."
406.
by orlp 4y ago
> It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. So what is the relationship then, in your eyes? I implemented my own branchless partition operator tha
407.
by orlp 4y ago
I will retract that you didn't mention memory-level parallelism back then, I lazily looked at the git blame and assumed it was introduced then. That was sloppy of me, sorry. > I described what made it fast I still partially disagree
408.
by orlp 4y ago
> Keep in mind that glidesort is partly derived from fluxsort and many of its techniques were directly inspired by fluxsort/quadsort, while several others are implemented in a similar or near-identical manner. This is in my opinion
409.
by orlp 4y ago
My results are on a 2021 Apple M1 MacBook Pro. And I'd like to reiterate it's not 100% apples to apples comparing fluxsort and glidesort directly. One would need to either completely implement glidesort in unsafe C throwing Rust-i
410.
by orlp 4y ago
I get these results for your benchmark on my machine: https://gist.github.com/orlp/d7123ede0143e15ab0f8a435b7dd10b... Either way, I am not surprised that glidesort is a bit slower than fluxsort on older machines. They&
411.
by orlp 4y ago
Try running with the latest nightly Rust (`rustup update nightly`) and with `cargo +nightly build --release`. EDIT: I'm sorry, you need to specify this in your Cargo.toml, my earlier command was incorrect: glidesort = { version =
412.
by orlp 4y ago
> Is that done by further recursing merges for larger merge sizes? Yes. > Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? Both. I haven't worked ou
413.
by orlp 4y ago
Correct.
414.
by orlp 4y ago
No, it is running serially. IPS4o is inherently more cache efficient due to having a very wide partition operator, making it better on machines with smaller caches, and better in general for strings (where no matter how cache-local your alg
415.
by orlp 4y ago
> How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? It does not ever allocate more than what it allocated at the start. > Is the some sort of back-pressure mech
416.
by orlp 4y ago
I haven't done a comparison yet (because I haven't gotten to really benchmarking the low-memory performance), but I will include it in the paper. The fact that glidesort can use small amounts of memory is honestly a happy coincide
417.
by orlp 4y ago
That is exactly right.
418.
by orlp 4y ago
I have some preliminary results I can share from the current draft paper: https://i.imgur.com/AUOJ1w0.png https://i.imgur.com/AP6DnIS.png Note that the four bottom sorts (RustSort, StdSort, Pdqsort, IPS4o)
419.
by orlp 4y ago
Not yet. I do aim to have open code for a benchmark including pdqsort, fluxsort, etc, accompanying my upcoming paper on glidesort. This would be in a separate repository. That code is very much... 'academic' right now, and needs p
420.
by orlp 4y ago
The allocation always happens once, at the start of the algorithm. The default allocation size is hard to describe in plain English, whereas the code is quite readable: const FULL_ALLOC_MAX_BYTES: usize = 1024 * 1024; const HALF_A

More ›