bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: fts: do not exhaust memory when processing million-entry directory


From: Pádraig Brady
Subject: Re: fts: do not exhaust memory when processing million-entry directory
Date: Thu, 18 Aug 2011 20:24:44 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:5.0) Gecko/20110707 Thunderbird/5.0

On 08/18/2011 02:53 PM, Jim Meyering wrote:
> A few weeks ago, I noticed that removing a directory with very many
> entries made rm -rf use an inordinate amount of memory.  I've fixed the
> underlying fts module to batch its readdir calls in the common case,
> thus to imposing a reasonable ceiling on memory usage.  The ceiling of
> ~30MB is reached for any directory containing 100,000 or more entries.
> 
> The way this change is designed, it induces no semantic change unless
> fts processes a directory with 100,000 entries or more, so normal
> testing would be unlikely to get good coverage.  In testing, I lowered
> the threshold of 100,000 first to 5, and then to 2.  In both cases,
> coreutils tools (modified to use this test version of fts) passed
> all of their regression tests.
> 
> I did the same with find (find.git v4.5.10-93-gd0c939a), but with
>  a threshold of just 10.
> 
> I mem-profiled that, just for fun and got this:
> (find /t/dir > /dev/null vs. 1M files in a tmpfs directory)
> 
>     KB
> 41.88^#               ::                        :
>      |#:   :::   :: : : :::::::::::  ::  : ::  ::::::  : ::@:::    ::: :: :::@
>      |# :::::::::: :::: : ::: :::::::::::::: ::::::: :@::: @::::::::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>      |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
>    0 
> +----------------------------------------------------------------------->Gi
>      0                                                                   4.530
> 
> Note that the maximum memory usage was barely 40KB (note, that's K as in kilo)
> and it ran for 4.5 Gi.  Note that that is using a ridiculously small test
> threshold of just 10.
> 
> Compare with find-4.5.9, which consumed over 1GB and required a few
> *more* instructions.
> 
>     GB
> 1.043^                  ##
>      |                  # :
>      |                 :# :::::
>      |                ::# :::::::
>      |               :::# ::::::::@
>      |              ::::# ::::::::@::::
>      |              ::::# ::::::::@::: :@
>      |            @:::::# ::::::::@::: :@::@
>      |           :@:::::# ::::::::@::: :@::@::
>      |           :@:::::# ::::::::@::: :@::@:::::
>      |          ::@:::::# ::::::::@::: :@::@:::::@::
>      |        ::::@:::::# ::::::::@::: :@::@:::::@:::@
>      |       :: ::@:::::# ::::::::@::: :@::@:::::@:::@:::
>      |       :: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@
>      |      ::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@::
>      |     :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::
>      |   :::::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@::
>      |  :: :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@::::
>      |  :: :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@:::::@:
>      | ::: :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@:::::@:::
>    0 
> +----------------------------------------------------------------------->Gi
>      0                                                                   4.683
> 
> While it is tempting to use a much lower-than-100,000 threshold,
> realize that doing so has a cost: a saved DIR* pointer (including a
> file descriptor) for each level in a hierarchy that has that many entries.
> 
> With the default threshold of 100,000, the maximum is under 30MB
> and slightly faster than the first run:
> 
>     MB
> 28.27^#
>      |#                        ::  :        :            :    :     :
>      |#            :  :        : :::      :::     :      :    :     :  :
>      |#            :  :        : : :     :: : :   :      :    :     :  :
>      |#            :  : ::     : : :     :: : :   :      :    :     :  :   : :
>      |#            : :: :      : : :     :: : :   :      :    :     :  : : : :
>      |#            : :: :      : : :     :: : :   :      :    :     : :: : : :
>      |#        :   : :: :      : : :     :: : :   :      :   ::     : :: : : :
>      |#    :   :   : :: :      : : :     :: : :   :      :   :: :   : :: : : :
>      |# :  :   :   : :: :     :: : :     :: : : :::      :   :: :   : :: : : :
>      |# :  :   :   : :: :     :: : :     :: : : : :      :   :: :   : :: : @ :
>      |# :  :   :   : :: :     :: : :   :::: : : : :      :   :: :   @ :::: @ :
>      |# ::::   :  :: :: :     :: : :  :: :: : : : :      :   :: :   @ :::: @ :
>      |# :: :   :  :: :: :     :: : :  :: :: : : : :      :   :: :   @ :::: @ :
>      |# :: :  ::  :: :: :  :: :: : :  :: :: : : : :      : ::::::  :@ :::: @ :
>      |# :: :  ::::::::: : ::  :: : :  :: :: : ::: :::::::: : ::::  :@ :::::@ :
>      |# :: :::::: ::::: : ::  :: : ::::: :: ::::: ::: : :: : ::::  :@::::::@ :
>      |# :: :: ::: ::::::: ::  :: : :: :: :: ::::: ::: : :: : ::::  :@::::::@ :
>      |#::: :: ::: ::::::: ::  :: : :: :: :: ::::: ::: : :: : ::::  :@::::::@ :
>      |#::: :: ::: ::::::: ::  :: : :: :: :: ::::: ::: : :::: :::::::@::::::@ :
>    0 
> +----------------------------------------------------------------------->Gi
>      0                                                                   4.481

Thanks for doing all this.
So the above is counting instructions rather than time?
30MB is still a large chunk of mem and typically will nuke a cache level,
or be much slower on a mem constrained system.
Perhaps it might be better to try to keep less than 1MB or so,
so as to be possibly more cache efficient, which seems
might not impact the number of instructions that much.
The output of `perf stat --repeat=5 find ...` would be interesting.
I'll try it on my sandy bridge laptop tomorrow evening
if you've not got sufficient hardware counters.

cheers,
Pádraig.



reply via email to

[Prev in Thread] Current Thread [Next in Thread]