`sort` does not finish for large one line file

[BAMF0]

I found that the sort utility does not finish to the stage of generating output for a large one line file. This issue is not found in the GNU implementation.

• OS release: Ubuntu Questing Quokka (development branch) 25.10
• uutils coreutils version: 0.2.0 (built from main commit: 9aaf603)

Reproduce

1. Generate a large file:
   oneline_4G.txt - a single line file consisting of a sequence of A's (4GB in size)

dd if=/dev/zero bs=1M count=4096 status=progress | tr '\0' 'A' |
head -c 4294967295 > oneline_4G.txt && echo >> oneline_4G.txt

2. Run coreutils sort sort on the file:

coreutils sort oneline_4G.txt

Reference Machine

• OS: Ubuntu Questing Quokka (development branch) 25.10
• Hardware Model: Lenovo Legion Slim 5 16IRH8
• Processor: 13th Gen Intel® Core™ i7-13620H × 16
• Memory: DDR5 16.0 GiB @ 5600 MT/s

[sylvestre]

does it happen in real life ? :)

[BAMF0]

@sylvestre I would think this usage of sort is very rare hahah!

I was comparing the performance of sort to the GNU implementation for a 'mean' file and noticed that while GNU finished within ~1 second, the uutils implementation simply would not finish.

[sylvestre]

yeah but maybe test with actual use cases first :)

[BAMF0]

@sylvestre Sure thing, will look into that! :)

I apologize for the provided scenario and its unrealistic nature. I performed a naive benchmarking on some coreutils using two irregular large files and this was one of the things I noticed.

Am I understanding correctly that the provided reproduction should mirror a use case that is more realistic?

[sylvestre]

oh, don't apologize, it is still a valid bug
for performance, i like to test with books

wget https://www.gutenberg.org/files/2701/2701-0.txt -O moby.txt
wget https://www.gutenberg.org/files/30613/30613-0.txt -O odyssey.txt
wget https://www.gutenberg.org/files/100/100-0.txt -O shakespeare.txt

[BAMF0]

@sylvestre Awesome, thanks for the advice!

Very good point actually. I realized that this form of naive benchmarking, while showing bugs, may paint an unjust picture in terms of real performance experienced by users. Will extend benchmarking to include more relevant inputs like these!

[eomanis]

yeah but maybe test with actual use cases first :)

One could consider "Preventing someone from performing a denial-of-service attack on a system using uutils sort to parse incoming data" a valid use case ;-)

[sylvestre]

sure, it is still a valid bug, no doubt :)

[loskutov]

GNU sort seems to avoid sorting for single-line inputs/buffers (which it doesn't mind allocating big enough to contain a 1G line): https://github.com/coreutils/coreutils/blob/v9.4/src/sort.c#L4069-L4070

[sylvestre]

Please don't share gnu code here. Our licenses are not compatible and we are not supposed to read it before working on our implementation

[kimono-koans]

One thing I see is that sort (and perhaps all uutils) is(/are) not reading large files as fast as it/they could be. One wants to read in as many bytes as possible in chunks, do any major ops on those bytes (like UTF8 validation), and then process to line output.

See for example my 1brc attempt: https://github.com/kimono-koans/1brc/blob/1c91b5c63cdff9bfc57d2ea00f7eff9237066250/src/main/rust/src/main.rs#L85

And my countwords: https://github.com/kimono-koans/countwords/blob/025ce95cad6d1ed665c3536d2f144b1384f77375/rust/fast-simple/main.rs#L57

[boomshroom]

Setting -S 4294967296 makes it finish in 9 seconds. Still pretty slow, but at least it finished. When checking strace, I noticed it kept making reads of 10240 bytes, which for a 4GiB file would require nearly 42 thousand reads. Setting a larger buffer size still had it start small at 8000 bytes, but then progressively doubled it until it reach around 4GiB.

[markg85]

Please don't share gnu code here. Our licenses are not compatible and we are not supposed to read it before our working on our implementation

Both are open source. GNU is GPL 3, this one is MIT. I don't think it's forbidden to look and get inspiration from it. It's not like a patent. For crying out loud, both are super open source projects, if those can't share than what the heck does open source even mean?

Edit

Seriously, 6 downvotes for my genuine disbelief that open source A can't sneak peak at open source B? It's ludicrous on it's own that people even think that way because we are all open source here. If looking "across the fence" is dangerous then it might as well be called closed source as the effect is the same. Heck, with this mentality you can even say that you're air-gapped and not allowed to look at any code or google anything at all because it "might" just originate from a incompatible license. Grow a spine and just look, cut the purism and just learn from each other. That is in the spirit of open source. I'll probably get more downvotes for this edit. Well, bring them on if that makes you feel good.

Edit 2

I'm disappointed, i was expecting at least 50 downvotes.. I'll just flip my screen and consider them upvotes 😉 If every downvote now improves the performance by 2x then this sort tool might become the fastest in it's class (ideally without crashing immediately). New algorithms would have to be invented. And all without looking at the neighbors 😂