Skip to content
Snippets Groups Projects
  • Yorhel's avatar
    0d314ca0
    Implement a more efficient hard link counting approach · 0d314ca0
    Yorhel authored
    As aluded to in the previous commit. This approach keeps track of hard
    links information much the same way as ncdu 1.16, with the main
    difference being that the actual /counting/ of hard link sizes is
    deferred until the scan is complete, thus allowing the use of a more
    efficient algorithm and amortizing the counting costs.
    
    As an additional benefit, the links listing in the information window
    now doesn't need a full scan through the in-memory tree anymore.
    
    A few memory usage benchmarks:
    
                  1.16  2.0-beta1  this commit
    root:          429        162          164
    backup:       3969       1686         1601
    many links:    155        194          106
    many links2*:  155        602          106
    
    (I'm surprised my backup dir had enough hard links for this to be an
    improvement)
    (* this is the same as the "many links" benchmarks, but with a few
    parent directories added to increase the tree depth. 2.0-beta1 doesn't
    like that at all)
    
    Performance-wise, refresh and delete operations can still be improved a
    bit.
    0d314ca0
    History
    Implement a more efficient hard link counting approach
    Yorhel authored
    As aluded to in the previous commit. This approach keeps track of hard
    links information much the same way as ncdu 1.16, with the main
    difference being that the actual /counting/ of hard link sizes is
    deferred until the scan is complete, thus allowing the use of a more
    efficient algorithm and amortizing the counting costs.
    
    As an additional benefit, the links listing in the information window
    now doesn't need a full scan through the in-memory tree anymore.
    
    A few memory usage benchmarks:
    
                  1.16  2.0-beta1  this commit
    root:          429        162          164
    backup:       3969       1686         1601
    many links:    155        194          106
    many links2*:  155        602          106
    
    (I'm surprised my backup dir had enough hard links for this to be an
    improvement)
    (* this is the same as the "many links" benchmarks, but with a few
    parent directories added to increase the tree depth. 2.0-beta1 doesn't
    like that at all)
    
    Performance-wise, refresh and delete operations can still be improved a
    bit.