HN user
For all practical matters it is xterm that has become the standard.
Like with web browsers, it is irrelevant what the standard states. The only thing that matters is that it displays correctly with the most popular / authoritative browser.
Web pages are increasingly bulky. A 3 MB page will take 1 second to load at 25 Mbps, so latency is often not the primary bottleneck.
Part of the problem may be that companies who own network infrastructure, and get paid for data usage, are also the ones that are the largest content providers.
This also comes with an electricity cost. We regulate efficiency for refrigerators, it might be time to add some sane limits to the largest content providers, which will also improve connectivity for those stuck with 2 Mbps.
Even if it's a thing, the idea that a teacher should take on the role of psychologists and figure out a child's optimal learning style should be preposterous to anyone with common sense.
It might work in combination with a software suite, with e-readers getting cheaper and more capable, and easily lasting through a school day, it's an option.
I think you pointed out the problem.
I suspect it has the same problem as ncurses: Not easy to learn, get proficient with, or rapidly produce something decent with.
I've been working on a project for a while that allows running any console program within it, and use text, keyboard, or mouse triggers to add a VT100 TUI, but it's uncomfortable to learn, very hard to get proficient with, and while it's possible to rapidly produce something decent, you're going to hit a hard wall producing something excellent.
Seems like speculation on top of speculation on top of speculation.
I wonder what the archeological data looks like, 6 burned down houses and a very active imagination?
Isn't the problem the absence of random DNA?
I wouldn't call random data 'complex', but it is easy to sequence when assembling short reads.
My main take away from the article was that we, apparently, need a time traveler to confirm/disprove Einstein's theory.
There's likely a market for office workers since there's a significant reduction of stress on the eyes.
You'd save about 0.5 kwh a day in electricity, more if the AC is running. So I could see them becoming popular once the price comes down. People who run 2 monitors might be interested as well.
MUDs are easily hosted abroad. Problem solved.
This reminds me of UK's 90% tax rate, which caused many multi-millionaires to leave the country.
I get the current time in microseconds, and increment by one nanosecond for each call between updates.
Problem solved for the next 200 years.
the coulombic efficiency of SSAB-PDBM was 84% at 4 C rate, which gradually decreased to 66% at 101 C rate.
Lithium batteries are over 95% efficient, so a long way indeed. Since the battery contains water, I assume it doesn't work below 0 C.
quadsort/fluxsort/crumsort author here.
For me there's a strong visual component, perhaps most obvious for my work on array rotation algorithms.
https://github.com/scandum/rotate
There's also the ability to notice strange/curious/discordant things, and either connect the dots through trying semi-random things, as well as sudden insights which seem to be partially subconscious.
One of my (many) theories is that I have the ability to use long-term memory in a quasi-similar manner to short-term memory for problem solving. My IQ is in the 120-130 range, I suffer from hypervigilance, so it's generally on the lower end due to lack of sleep.
I'd say there's a strong creative aspect. If I could redo life I might try my hand at music.
https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc...
As you can see, quadsort 1.1.4.1 used 2 instead of 4 writes in the bi-directional parity merges. This was in June 2021, and would have compiled as branchless with clang, but as branched with gcc.
When I added a compile time check to use ternary operations for clang I was not adapting your work. I was well aware that clang compiled ternary operations as branchless, but I wasn't aware that rust did as well. I added the compile time check to use ternary operations for a fair performance comparison against glidesort.
https://raw.githubusercontent.com/scandum/fluxsort/main/imag...
As for ipnsort's small sort, it is very similar to quadsort's small sort, which uses stable sorting networks, instead of unstable sorting networks. From my perspective it's not exactly novel. I didn't go for unstable sorting networks in crumsort to increase code reuse, and to not reduce adaptivity.
"pick a few fixed sizes and handle the rest by rounding down then a few steps of insertion sorting."
I'm late to the party, but this sounds a lot like quadsort's small array handling:
Sort 4, 8, or 16 elements using unrolled parity merges, and handle the rest with insertion sorting.
An unrolled parity merge can be viewed as a stable sorting network. I never added unstable sorting networks to crumsort due to wanting to keep the code size low, and perhaps the mistaken idea that it would reduce adaptivity, as crumsort is likely to scramble partially sorted input.
The gif is indeed a bit rushed, I'll see if I can get it looking a bit better soon-ish.
The video is up on YouTube where it can be paused.
Edit: Just now seeing you asked about updates.
I added support for clang's branchless ternary comparisons, and increased the granularity of the analyzer.
There's a list of online MUDs that are still in active development here:
Especially on Windows you'd be better off using PuTTY or TinTin++ to connect, since Microsoft's telnet is pretty much broken:
It is said that getting ripped off is the highest form of flattery.
The FOSDEM talk indeed addressed my worries.
I actually don't see the ping-pong merge as a personal accomplishment, it's not that novel a concept, at best I popularized it. The actual performance gain from it is minimal, maybe 1%, though that is perhaps the most interesting thing, that data moves are practically free. And I would like to take full credit for that observation!! :-)
I've been most impressed with ChatGPT's ability to analyze source code.
It may be able to tell you what a compiled binary does, find flaws in source code, etc. Of course it would be quite idiotic in many respects.
It also appears ChatGPT is trainable, but it is a bit like a gullible child, and has no real sense of perspective.
I also see utility as a search engine, or alternative to Wikipedia, where you could debate with ChatGPT if you disagree with something to have it make improvements.
As I wrote previously, thank you for fully addressing all my concerns in your recent FOSDEM presentation.
While it would have been outside the scope of the presentation, and time being short, quadsort does present an interesting alternative to handling the merge length problem powsort tries to solve.
I've honestly been unable to detect any notable instruction-level parallelism on my own hardware. I suspect there may not be any? It'll be interesting to get to the bottom of this.
As for quadsort, it does contain a guarded bidirectional merge. I published it after you started working on glidesort however. It was always on my todo list, but I do get tired of programming from time to time.
As for unguarded parity merges, it was indeed one of my brighter moments when I came up with that.
Anyways, once again, thanks for addressing my concerns in the FOSDEM presentation, and if it wasn't clear, I think you did some really excellent work on glidesort.
I've just watched your FOSDEM presentation and to put it simply, thank you for addressing all the issues I had.
I felt pretty uneasy about what I perceived as a situation where you could end up taking full credit for innovations I was first to develop and publish. I do realize this could be all in my head. Anyways, I'm at ease now and I hope my assertions didn't create any ill will between us.
As for your arguments, they're pretty sound and I find no reason to doubt you. It was never my intention to appear dismissive towards your work, writing glidesort was no easy matter and the merge routines are a significant improvement upon Timsort/Powersort.
That code was indeed a bit unorganized, I updated bench.c in wolfsort's github, hopefully that'll fix it.
Would you mind giving your 2 cents on this topic?
https://news.ycombinator.com/item?id=34650406
You are probably more familiar with this topic than most.
It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts.
Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge.
On his github he mentions timsort 2 times, and powersort 5 times. So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort.
There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain.
Perhaps I'm being overly sensitive?
This is what quadsort's README stated in early 2021:
"Since the parity merge can be unrolled it's very suitable for branchless optimizations to speed up the sorting of random data. Another advantage is that two separate memory regions can be accessed in the same loop with no additional overhead. This makes the routine up to 2.5 times faster on random data."
I described what made it fast and it was obvious there was general applicability. If I understanding your reasoning correctly, because you took inspiration from my more advanced unguarded two directional merge, you feel like a guarded two directional merge is some new novel discovery.
This is a very contentious line of reasoning.
Subsequently you then proceed to give me zero credit for branchless merging in your Youtube presentation, instead referencing a branchless merge that gave a 10-20% speed-up instead of quadsort's 150% speed-up. You also claimed in the presentation there were no bidirectional branchless algorithms written to date, this is simply not true.
This does upset me. It would be a simple matter, and the right thing, to point out that quadsort introduced bidirectional branchless merging.
As for your work to increase the memory regions from 2 to 4. This is easily conceived, but indeed quite challenging to actually implement.
Those are some awfully large array sizes. Not something I ever had the patience for to sit out, or optimize for, as it didn't seem like the most common real-world scenario.
One thing glidesort appears to do extremely well is to branchless merge till the very end, this gets quite tricky when memory constrained. It does not seem worth it intuitively, but judging from the performance of rotate mergesort, it probably is.
If the last presentation's benchmark still goes, blitsort is significantly faster.
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 not adequately explained in the presentation on youtube.
The main difference is that glidesort uses timsort's approach to adaptive sorting rather than quadsort's, though it uses quadsort's novel method for cost-effective branchless merging.
Glidesort tries to access 4 memory regions instead of 2, primarily with the bidirectional partition, an approach I implemented in 2021, but rejected because it was causing degraded performance for expensive comparisons. This does however result in a very different visualization which can give the impression it is unrelated. The general approach to stable partitioning is likely nearly identical to fluxsort.
As for why blitsort is fast, it's likely due to trinity rotations and monobound binary searches. Possibly also a more optimal overall partitioning strategy.
I haven't spend too much time on blitsort however, so there are likely further improvements to be made.
I went ahead and updated bench.c for the wolfsort github.
I'm planning to update wolfsort soon-ish. I did some work on a dropsort hybrid, like rhsort, though it's slower overall because I'm not quite brave enough to match the level of insanity (I mean this in a good way) that rhsort engages in.
The latest fluxsort is probably identical on random, the new analyzer might perform slightly better on modern hardware.
Probably safer to stick with wolfsort as I do tend to make sure that works with rhsort when I update.
I recently upgraded fluxsort, you might want to give v1.1.5.4 a spin. I also updated the benchmark to use actual natural runs and be less favorable to rhsort, sorry. ;-)
I'm not surprised fluxsort is slightly faster, it's heavily optimized for gcc -O3.
Since the primary techniques that give glidesort it's speed were copied from fluxsort and quadsort I'm expecting very similar performance, and possibly significantly worse performance on strings due to accessing 4 memory regions.
Have you gotten it working with the wolfsort benchmark?
The latest quadsort version sorts 8 elements at a time. It's not really a sorting network, and it wouldn't have worked very well prior to branch prediction, or having a multitude of registers.
So basically all the work that had been done for decades has become useless because it was carried out on different hardware. It's possible that 2 or 3 people wrote an algorithm similar to quadsort, and discarded it for being slow.
Anyways, quadsort is in fact exceptionally fast. I understand people doubt the benchmark and think it is rigged or something. I assure you it is not, plenty of people have checked and ran the benchmark themselves.
Quadsort makes more comparisons than timsort, but it has far better branch prediction for random data and far less overhead under the hood.
While a switch might seem bad, in the case of random data quadsort turns 1.5 branch mispredictions into 0.84 branch mispredictions. My upcoming release of quadsort 1.1.5.4 will improve that further.
This is a difficult topic to comment on for someone who isn't 100% in the know, and I often make incorrect assumptions myself.
It would be interesting indeed to get the actual energy efficiency, but quadsort being 2-3x faster than timsort on random data pretty much guarantees it is. I'm not aware of an easy method to measure energy consumption, but it would be a better metric in this day and age.
As for mergesort vs quicksort, this is pretty much a draw and it heavily depends on data type and comparison type. Fluxsort so far appears to confirm that a hybrid mergesort/quicksort is the best overall by taking advantage of the strengths of both algorithms.
Adaptation is coming along slowly but steadily. Several people have started incorporating my branchless bidirectional merge and branchless stable partition concepts, among other things, as fluxsort contains quite a few novelties. My work on binary searching and array rotations could be even more important to reducing the energy footprint.
Quadsort's author here.
This is the first time I've heard quadsort being called esoteric. It isn't much more complex than Timsort. It is however challenging to port ~1000 lines of code that can be tedious to debug. If you make one simple error/typo you could be stuck for hours in debugging hell.
Hence I recently published piposort, which is ~150 lines and pretty basic, while still offering excellent performance. Not as good as quadsort, but it could make for a stepping stone in a porting effort.