Performance of nnn vs. ls

https://github.com/jarun/nnn/wiki/performance

by apjana • 7 years ago

84 57 7 years ago

github.com

kekebo• 7 years ago

A comparison to exa[0] would be interesting as well

[0] https://github.com/ogham/exa

apjana19• 7 years ago

I am on a much faster system right now. From 2 sample runs of each, ls is consistently way (~5 times) faster than exa:

exa:

    run1:
    0.03user 0.02system 0:00.11elapsed 56%CPU (0avgtext+0avgdata 8672maxresident)k
    208inputs+0outputs (1major+1333minor)pagefaults 0swaps

    run2:
    0.04user 0.00system 0:00.13elapsed 42%CPU (0avgtext+0avgdata 8560maxresident)k
    0inputs+0outputs (0major+1310minor)pagefaults 0swaps

ls:

    run1:
    0.00user 0.01system 0:00.02elapsed 69%CPU (0avgtext+0avgdata 3812maxresident)k
    0inputs+0outputs (0major+303minor)pagefaults 0swaps

    run2:
    0.01user 0.00system 0:00.02elapsed 62%CPU (0avgtext+0avgdata 3840maxresident)k
    0inputs+0outputs (0major+305minor)pagefaults 0swaps

eridius2• 7 years ago

How about lsd? https://github.com/Peltoche/lsd

ape4• 7 years ago

I would be nice to use some of these techniques to speed up * (wildcard) in bash

SonOfLilit5• 7 years ago

Not sure they're relevant? * doesn't sort or filter by metadata, and since it's all strings touched only once I guess there's not much in the name of data structures to not paragraph-align?

kgwxd• 7 years ago

Just before this made it to the front page, I happened to see this toot about slow ls: https://ubuntu.social/@Simon/102054773088776436

I'm curious if that would make a difference.

apjana19• 7 years ago

For reference, from the system where the numbers were taken:

     $ echo $LS_COLORS
     
     $

LS_COLORS wasn't set. The readings were taken for ls default performance.

BlackLotus89• 7 years ago

LS_COLORS mustn't be set for colors to be used. If you unset it the default color schema will be used.

There was an article about this posted to HN a week ago https://news.ycombinator.com/item?id=19761159

JdeBP2• 7 years ago

You'll find the original discussed on Hacker News at https://news.ycombinator.com/item?id=19761159 .

mereel• 7 years ago

This seems pretty cool, but why does the source code have to be contained within a single 4000 line file[0]? I'm fairly ignorant of the design patterns used in Linux tool development, but it seems like splitting this into a few more files could make the code a little easier to understand/maintain.

[0] https://github.com/jarun/nnn/blob/master/src/nnn.c

groovybits2• 7 years ago

I believe the concept of nnn is that all the source code is contained in one file. If you wish to add extensions onto nnn, you can then write a c file and include it in nnn.c

apjana19• 7 years ago

Extensions are (mostly) POSIX-compliant shell scripts (though they can be compiled binaries also). I have (kind of) explained in the main thread the reason I never felt the need of re-factoring the code into multiple files.

apjana19• 7 years ago

I wish some open source enthusiast offered to contribute in return for the re-factoring you are looking for ;). I am (generally speaking) the lone developer of this project for 2 years. And with ctags and cscope I don't find any problem in developing.

spillybones• 7 years ago

For comparison, the `ls` in GNU coreutils is a single 5,310 line C file[0], so I think nnn's codebase pretty much par for the course (nnn has much more functionality than ls with 1K fewer lines of code). Splitting into different files makes more sense when you have a bunch of independent subsystems, but nnn is just a file manager. As someone who has dug through nnn's source code enough to track down a bug and propose a fix, I found it to be a pretty easy codebase to work with.

[0] https://github.com/coreutils/coreutils/blob/master/src/ls.c

SonOfLilit5• 7 years ago

Seems like running `ls` takes twice as long as running `nnn`, but I wonder how long it takes to type each...

    $ ipython
    In [1]: %time input()
    ls
    Wall time: 324 ms
    Out[1]: 'ls'
    
    In [2]: %time input()
    nnn
    Wall time: 711 ms
    Out[2]: 'nnn'

In other words, `nnn` takes twice as long (on my setup, including a qwerty keyboard and my fingers and muscle memory) and it's on the same order of magnitude as running them, so I guess they're more or less equal.

This is all tongue in cheek, but my point is that the important optimization is of user productivity and not of runtime, and in that respect as far as I'm aware `Total Commander` on Windows and its open source plugin-compatible clone `doublecmd` that runs on both Windows and Linux are far superior to anything else in the market. Don't let the Windows-3.11 reminiscent design scare you, with Total Commander you'll be as productive doing complex file operations as those vim masters are doing complex text transformations, and you won't ever be able to go back to any other file manager.

edit: I misread, actually typing them is a decimal order of magnitude slower than running them on 2083 files.

apjana19• 7 years ago

`nnn` is covered there. It's not a one-shot utility, but a file manager.

Also, you would be happy to know I use the following alias on my system to fire it in 162 ms:

    alias n='nnn -isl'

SonOfLilit5• 7 years ago

Naturally :-) That's why "tongue in cheek". I still can't imagine myself switching from Total Commander, it's so amazingly powerful.

jandrese2• 7 years ago

I alias 'ls' to 'd' when I'm setting up an environment.

eindiran3• 7 years ago

Do you mean that you have an alias like this:

  alias d='ls'

Or is there a program called `d` that is a faster version of `ls` that you're aliasing `ls` to?

SonOfLilit5• 7 years ago

`d` is taken by the much more important command `git diff`. I don't even have an alias for `ls`, I seldom use it, I mostly run `s` (which is an alias of `git status` of course).

pvg2• 7 years ago

Windows-3.11 reminiscent design

Strictly speaking, it's an MS DOS design - a descendant of Norton Commander.

JdeBP2• 7 years ago

The formal name is an orthodox file manager.

SonOfLilit5• 7 years ago

I meant the graphic design, which is what put most people off.

mochomocha• 7 years ago

Without variance information, the numbers reported are pretty meaningless. A single run doesn't make a benchmark.

apjana19• 7 years ago

They were kind of consistent across multiple runs.

lwhsiao• 7 years ago

I'll give a quick plug for hyperfine [0], which makes running a series of benchmarks really easy.

[0] https://github.com/sharkdp/hyperfine

peterwwillis• 7 years ago

What's the use case where you need 'ls' to be fast?

OJFord• 7 years ago

Interactive

agumonkey• 7 years ago

timing should be amortized, when `nnn` (or similar) is on you have state and can think and operate infinitely faster

apjana19• 7 years ago

Absolutely! I personally use xfce4-terminal is drop-down mode to preserve my contexts over days.

eindiran3• 7 years ago

I just downloaded `nnn` from apt and I am not seeing this performance at all. `ls` is blazingly faster than `nnn` on this machine. I am seeing a speedup over `ranger`, but both are taking quite a while for a directory with 196388 files in it.

  time /usr/bin/nnn -S /local

  /usr/bin/nnn -S /local  0.04s user 0.36s system 15% cpu 2.503 total

  time /usr/bin/ranger /local

  /usr/bin/ranger /local  0.31s user 0.02s system 12% cpu 2.667 total

  time /bin/ls /local

  /bin/ls /local  0.00s user 0.00s system 86% cpu 0.002 total

Perhaps this is related to the `$LS_COLORS` environment variable, as discussed in a few other comments? It is set on this machine.

  echo $LS_COLORS

  no=00:fi=00:di=34:ow=34;40:ln=35:...<many more entries>...:*.sqlite=34:

apjana19• 7 years ago

The version available on apt is older. The performance numbers are from master. I am on a device with SSD now and `nnn` master consistently gives a better performance in 3 runs.

Here are the numbers I see with $LS_COLORS set to:

    ex=00:su=00:sg=00:ca=00:

    nnn (still shows dir colors as it's designed to):
    0.00user 0.00system 0:00.01elapsed 33%CPU (0avgtext+0avgdata 3420maxresident)k
    0inputs+0outputs (0major+319minor)pagefaults 0swaps

    ls (no colors):
    0.00user 0.01system 0:00.02elapsed 60%CPU (0avgtext+0avgdata 3724maxresident)k
    0inputs+0outputs (0major+297minor)pagefaults 0swaps

And going deeper, with the same $LS_COLORS, see the difference in the number of calls (no wonder `nnn` outperforms `ls`):

    $ time strace -c /usr/local/bin/nnn /usr/bin | wc -l
    % time     seconds  usecs/call     calls    errors syscall
    ------ ----------- ----------- --------- --------- ----------------
     82.55    0.004592           2      1988           newfstatat
      8.47    0.000471         118         4           getdents
      2.82    0.000157           3        58         1 stat
      1.89    0.000105         105         1           inotify_add_watch
      1.64    0.000091           9        10           brk
      1.33    0.000074           5        15           close
      0.23    0.000013           1        14           openat
      0.18    0.000010           3         4           write
      0.18    0.000010           0        22         2 ioctl
      0.13    0.000007           0        15           fstat
      0.13    0.000007           1        14           mmap
      0.13    0.000007           7         1           inotify_rm_watch
      0.11    0.000006           1         8           read
      0.11    0.000006           6         1         1 unlink
      0.07    0.000004           4         1           sysinfo
      0.05    0.000003           3         1           lseek
      0.00    0.000000           0         2           lstat
      0.00    0.000000           0        10           mprotect
      0.00    0.000000           0         1           munmap
      0.00    0.000000           0         9           rt_sigaction
      0.00    0.000000           0         9         7 access
      0.00    0.000000           0         1           execve
      0.00    0.000000           0         1           arch_prctl
      0.00    0.000000           0         1           inotify_init1
    ------ ----------- ----------- --------- --------- ----------------
    100.00    0.005563                  2191        11 total
    0.03user 0.01system 0:00.06elapsed 74%CPU (0avgtext+0avgdata 3424maxresident)k
    2968inputs+0outputs (7major+541minor)pagefaults 0swaps
    0
    
    $ time strace -c ls -l /usr/bin | wc -l
    % time     seconds  usecs/call     calls    errors syscall
    ------ ----------- ----------- --------- --------- ----------------
     32.03    0.004882           2      1989           lstat
     30.42    0.004636           2      1989      1989 lgetxattr
     22.45    0.003421           2      1548      1548 getxattr
      6.57    0.001002           2       442           readlink
      6.15    0.000938         235         4           getdents
      0.45    0.000068           2        33         5 openat
      0.43    0.000066           6        11           munmap
      0.31    0.000047           1        34           close
      0.30    0.000045           1        40           mmap
      0.26    0.000040           2        17           lseek
      0.20    0.000031           1        30           fstat
      0.10    0.000015           4         4         4 connect
      0.09    0.000014           3         5           brk
      0.07    0.000011           3         4           socket
      0.07    0.000010           0        31           write
      0.06    0.000009           9         1           mremap
      0.03    0.000005           0        17           read
      0.00    0.000000           0        20           mprotect
      0.00    0.000000           0         2           rt_sigaction
      0.00    0.000000           0         1           rt_sigprocmask
      0.00    0.000000           0         2         2 ioctl
      0.00    0.000000           0        12        12 access
      0.00    0.000000           0         1           execve
      0.00    0.000000           0         2         2 statfs
      0.00    0.000000           0         1           arch_prctl
      0.00    0.000000           0         1           futex
      0.00    0.000000           0         1           set_tid_address
      0.00    0.000000           0         1           set_robust_list
      0.00    0.000000           0         1           prlimit64
    ------ ----------- ----------- --------- --------- ----------------
    100.00    0.015240                  6244      3562 total
    0.04user 0.06system 0:00.09elapsed 114%CPU (0avgtext+0avgdata 3676maxresident)k
    0inputs+0outputs (0major+521minor)pagefaults 0swaps
    1989

eindiran3• 7 years ago

Very cool. Do you know what the timeline is for getting the contents of master into the version packaged for apt?

On the topic of `ls` making many more syscalls than `nnn`, its interesting that `nnn` is using the `newfstatat` syscall. Is that capturing the information that the `lstat`, `lgetxattr`, and `getxattr` syscalls are getting for `ls`? If so, will that potentially limit this speed up to architectures that make use of the newer `newfstatat` syscall?

ordu3• 7 years ago

no floating point arithmetic

Does it really makes things faster? I cannot find enough motivation to test it myself, but after I've read Abrash's Black Book, I got impression that floating point operations are at least as fast as operations on integers and in some cases they are faster.

While I see reasons to not use FPU, I believe that speed is not among of them. At least on x86 where a fast hardware implementation of floating point numbers exists.

fourier_mode• 7 years ago

I believe all these utilities must be memory bound, and having short `int`s instead of `float`s would be a less traffic on the bus.

apjana19• 7 years ago

numbers here: https://github.com/jarun/nnn/pull/84

ordu3• 7 years ago

Thank you. It seems have nothing to do with speed of computation, difference in speed caused by formatting inside snprintf. If I'm right, it explains why integers are faster in your case and slower in the Black Book.

kazinator2• 7 years ago

no floating point arithmetic was still a bit of a coding mantra circa 1993.

kazinator2• 7 years ago

That's nice; ls was fast enough for my personal use more than twenty years ago.

I don't have that many more files to list today, just some vastly larger ones.

Speaking of twenty years ago, that's about when some of the most stubborn programmers had quit the habit of using shifts instead of multiplies, and embraced floating-point.

apjana19• 7 years ago

`nnn` is not a replacement of `ls`, it's a file manager. This is a comparison of the speed while listing. Turned out we don't need floating point for a file manager, so we left that for some other useful work.

zeroimpl• 7 years ago

I’m not surprised there are a bunch of optimizations which could be made to “ls”. On a related note, I once looked at source code for “rm” (specifically “rm -rf”) and was surprised how inefficient it seemed. Not sure if it has changed since, but it would stat files before deleting and do various permissions checks - things that could be accomplished by just letting the kernel try to do the delete and then checking the status code. That ought to be faster 99% of the time.

apjana19• 7 years ago

There are several aspects of `rm` which seemed safer rather than re-writing the defensive logic. Though, it can be done in the code without any dependency, I agree.

Performance of nnn vs. ls

Related Stories