8

I have large text file (1.5 G),

I want to know what the fastest and more reliable tool in Linux is.

I usualy use:

awk '!x[$0]++' file.txt

But when I use htop command I see my memory usage is increasing.

I want to know what is the fastest and more reliable one for huge files.

uniq?
sort?
sed?
awk?

Why?

4
  • Have you tried running them, possibly with time?
    – choroba
    May 10, 2014 at 12:08
  • time is important and also memory usage and reliability(I mean which one does his job accurately)
    – MLSC
    May 10, 2014 at 12:10
  • Not yet ... But I did some tests before...and ask somewhere, some guys told me awk is the best..but in htop...I see memory usage is increasing
    – MLSC
    May 10, 2014 at 12:11
  • 3
    @MortezaLSC: It is a trade off. The faster the program is, the more memory is used.
    – cuonglm
    May 10, 2014 at 12:33

3 Answers 3

20

Let's consider how each solution works.

  • uniq This requires that the file already be sorted. If not, you have to pipe it through sort first, which means that sort has to read the entire file into memory, reorder it (O(n log n)), and then write it into the pipe. The work of uniq is very cheap, since it only has to compare adjacent lines of its input.

  • sort -u This combines the work of sort | uniq. This has to collect all the unique inputs into memory like the awk script does, but it also then wastes time sorting them before producing the output. This is O(n log n), although in this case n is the number of unique items, not all the inputs. So it's better than the pipe.

  • sed I'm not sure why you listed this, as I can't think of a good way to do this with sed at all. Maybe if you first sort it and pipe to a sed script, there's a way to compare adjacent lines. So sed would just be doing what uniq does, and uniq probably does it about as efficiently as possible.

  • awk This is likely the best because it only does the minimal amount of work necessary. As it reads each line, it does an efficient hash lookup to see if the line is already in its memory, and only stores the unique lines as hash keys, and a counter as the value. (If the line wasn't previously present, the condition will be true, so the line will be printed. Otherwise it won't.) This uses O(n) time and O(uniq n) memory.

Every method will use a considerable amount of memory, either for sorting the input or keeping track of which inputs have seen so they can remove duplicates.

6
  • 1
    +1 The explanation regarding awk also explains why it uses increasing amounts of memory. Anything which does a sort will end up doing this as well, only 1) it will probably use it all at once, 2) it may use slightly more, depending on the number of unique vs. duplicated keys.
    – goldilocks
    May 10, 2014 at 13:09
  • @Barmar pardon, But when I have a large file(16 G) with memory capacity 8G , So what is going to happen with my memory?
    – MLSC
    May 10, 2014 at 13:30
  • 8
    @goldilocks, sort resorts to temporary files (in an intelligent way) to avoid filling up the memory. Its memory usage is bound. The boundary is customisable with some sort implementations. It's more efficient that letting the system swapping memory randomly to disk (which also affects also applications on the system). May 10, 2014 at 15:19
  • That's true. So if you run into a case where awk runs out of memory, sort may be the only solution because it has been designed to deal with this. On the other hand, all that disk reading and writing will slow it down, so it will probably take a long time to complete. If you're dealing with such large amounts of data, you should probably be using a DBMS rather than text files.
    – Barmar
    May 10, 2014 at 19:11
  • @Barmar How did you deduce that time of reordering increases as O(n log n)? Or just you know it from elsewhere?
    – jimmij
    Oct 10, 2014 at 17:17
3

I just wanted to point out that gnu uniq seems terribly slow, even on a sorted list.

I just tried getting a list of directory prefixes from a list of sorted filenames:

$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes

36.7GiB 0:07:41 [81.4MiB/s]

$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2

36.7GiB 0:03:14 [ 193MiB/s]

$ pv all_files  | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3                                        
36.7GiB 0:02:18 [ 270MiB/s] 

sort -u seems twice as fast as uniq, and this is with sort reading from stdin and writing to stdout, so I don't see it do any parallelization yet. I have no idea why uniq should be so much slower then sort, since it doesn't have to sort the list...

The outpuf of this command is very small (there are a lot of duplicates), only 264kb and sort terminates instantly after pv is done.

The same speeds remain if you turn around the order of the commands, my flow is limited by cpu time here, not disk access and caches (I only have 8GB of RAM and my swap is not used)

I'm running this on a fedora 31 machine with gnu coreutils sort and uniq and gnu awk; locale is set to en_US.UTF-8

UPDATE, since this intrigued me quite a bit I did some more tests, let's ge the cut part out of the way, and make sure the file is nicely sorted

cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test

This takes 8.4 minutes. test is now 7.9GB big

let's run these tools on the file instead of in a pipe, this will allow these tools to do some more optimization, like sort will multi thread. and also from a faster ssd.

You might not notice that sort is also taking a lot of memory, since it does clever tricks with temp files in /tmp which might be tmpfs and will be in your ram ( Try sorting a file bigger then /tmp, you will run into space issues, that's why I need the -T . flag in the above command)

$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps

$ time awk '!x[$0]++' test > /dev/null                                                                                                                             
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                  
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps

So it seems your awk solution is the fastest of these 3, and actually uses the least memory

update2 and now with a simpler locale

$ export LC_ALL=c
$ time sort -u test > /dev/null                                                                                                                                             1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k

$ time awk '!x[$0]++' test > /dev/null                                                                                                                                1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                               
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps

This time uniq does win the race... as Stéphane Chazelas hints to in the comments, setting your locale to C makes sort and uniq a whole bunch faster!

2
  • What implementation of sort and uniq? What locale? Apr 20, 2020 at 14:36
  • If using mawk, the awk solution is still the fastest even beating the GNU tools with LC_ALL=c. Mar 25 at 15:56
0

I've found that sort seems to be the fastest uniq tool as shown here --> Fastest way to delete duplicates in large wordlist?

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .