GNU bug report logs - #10877
[sort] too eager to use temp files

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 10877 in the body.
You can then email your comments to 10877 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
To: bug-coreutils <at> gnu.org
Subject: Wimpy external files. 
Date: Fri, 24 Feb 2012 14:53:57 +0100

Hi,

I understand the need for external temporary files. (I rewrote dos 3.3
sort for personal use when I got my first computer in 1987). 

However on my 8G machine sort imho is allowed to use say 200M or maybe
even 2000M of core memory. If you write a temporary file every
20Mb, there will be such a whole lot of them. 


zebigbos:/> l /tmp/sort* | wc -l
163
zebigbos:/> free
             total       used       free     shared    buffers     cached
Mem:       8264484    8100420     164064          0     376756    6853884
-/+ buffers/cache:     869780    7394704
Swap:            0          0          0
zebigbos:/> 


It seems that I may be allowed to set this with the -S option. The
manual does not mention a default. A more sensible default would be in
order.

	Roger. 


-- 
** R.E.Wolff <at> BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.

Message #8 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Cc: 10877 <at> debbugs.gnu.org
Subject: Re: bug#10877: Wimpy external files.
Date: Fri, 24 Feb 2012 09:28:02 -0800

I think 'sort' by default uses 1/8 of physical memory.
It sounds like that calculation isn't working on your host;
if so, it'd be nice if you could dive into the code and see why.

Message #11 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 10877 <at> debbugs.gnu.org, Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Subject: Re: bug#10877: Wimpy external files.
Date: Fri, 24 Feb 2012 19:00:48 +0100

On Fri, Feb 24, 2012 at 09:28:02AM -0800, Paul Eggert wrote:
> I think 'sort' by default uses 1/8 of physical memory.
> It sounds like that calculation isn't working on your host;
> if so, it'd be nice if you could dive into the code and see why.

OK. I'll look into it. The server where I observed the 20M files has
8G RAM, and is currently very busy with its primary task (serving
files).

The server runs 32bit userspace and an PAE kernel. 

I checked if I can reproduce the problem on my workstation that
would be available for testing. 

My workstation has 8G ram and is fully 64-bit. (i.e. kernel +
userspace).

On my workstation I get 34M files.... So problem reproduced. It is
using 30 times smaller files than what you predict it would.

Analysis so far: 
-S 2% results in about 160Mbytes of core memory used, and temporary
files of about 114Mbytes. 

My conclusion is that physmem_total() is working. 

After a bit of instrumentation I get: 


default sort size: avail=1946.183594M, total=8001.156250M, mem=1946.183594M
size is now: 1946M
after rlimit size is now: 1946M
after margin size is now: 973M
after rlimitrss size is now: 973M
returning: 973M

so also the function "default_sort_size" seems to be working. I have
to leave now. More later. 

	Roger.


-- 
** R.E.Wolff <at> BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.

Message #14 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 10877 <at> debbugs.gnu.org, Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Subject: Re: bug#10877: Wimpy external files.
Date: Sat, 25 Feb 2012 13:56:42 +0100

On Fri, Feb 24, 2012 at 09:28:02AM -0800, Paul Eggert wrote:
> I think 'sort' by default uses 1/8 of physical memory.
> It sounds like that calculation isn't working on your host;
> if so, it'd be nice if you could dive into the code and see why.


OK. I've diven in to the code a bit and after some more
instrumentation I get:

assurancetourix:~/sort/sortproblem/coreutils-8.5/src> tail -n +10 du.unsorted | ./sort
sort_buffer_size: bound=0M
unknown filesize sortsize=0M
unknown filesize guessing=1M
default sort size: avail=217.234375M, total=8001.207031M, mem=1000.150879M
size is now: 1000M
after rlimit size is now: 1000M
after margin size is now: 500M
after rlimitrss size is now: 500M
returning: 500M
got size_bound=500M / file_size = 1M
worstcase=49M  (worst_case_per_input_byte = 49
returning  size=49M

The core of the problem is that when the filesize cannot be determined
(as in this case because it's a pipe), it guesses the filesize to be
1M, and then uses "worstcase" calculations to come to "about 50M" for
the buffer size.

This happens in the function around line 1380 in sort.c

I don't think that any guessing should be done if we cannot determine
the filesize. In that case we have great heuristics to come up with a
reasonable buffer size without the filesize.

Similarly, there is a logic error in the code that determines the
maximum memory to use: You said it was supposed to use 1/8th of total
memory. However it then takes another factor of two "margin". I think
the margin should not be applied to "total mem/8". (the quick fix is
to just turn that "8" in the code into a "4".)

Similarly, I think that it is reasonable to use "all available"
memory. This "all available" is really free memory, so there should
not be any risk in trying to use it all. Of course there are RSS
limits. Those should apply, with the appropriate margin. 

Here is my suggestion for default_sort_size. I've left the
instrumentation/debug in there. (I don't understand why
SIZE_MAX/1024/1024 evaluates to -1 on my machine, but I don't really
care. It seems to work....).


/* Return the default sort size.  */
static size_t
default_sort_size (void)
{
  /* structure of this function: 
   *
   * We start with too big a number, and then "filter" it as we see
   * fit.
   */ 
     
  double mem, total, avail;
  struct rlimit rlimit;
  size_t size; 

  /* Let SIZE be MEM, but no more than the maximum object size or
     system resource limits.  Avoid the MIN macro here, as it is not
     quite right when only one argument is floating point.  Don't
     bother to check for values like RLIM_INFINITY since in practice
     they are not much less than SIZE_MAX.  */

  size = SIZE_MAX;

  if (getrlimit (RLIMIT_DATA, &rlimit) == 0 && rlimit.rlim_cur < size)
    size = rlimit.rlim_cur;
  fprintf (stderr, "after rlimit size is now: %dM\n", size/1024/1024);

#ifdef RLIMIT_AS
  if (getrlimit (RLIMIT_AS, &rlimit) == 0 && rlimit.rlim_cur < size)
    size = rlimit.rlim_cur;
#endif

  /* Leave a large safety margin for the above limits, as failure can
     occur when they are exceeded.  */
  size /= 2;
  fprintf (stderr, "after margin size is now: %dM\n", size/1024/1024);

#ifdef RLIMIT_RSS
  /* Leave a 1/16 margin for RSS to leave room for code, stack, etc.
     Exceeding RSS is not fatal, but can be quite slow.  */
  if (getrlimit (RLIMIT_RSS, &rlimit) == 0 && rlimit.rlim_cur / 16 * 15 < size)
    size = rlimit.rlim_cur / 16 * 15;
#endif
  fprintf (stderr, "after rlimitrss size is now: %dM\n", size/1024/1024);

  /* Let MEM be available memory or 1/8 of total memory, whichever
     is greater.  */
  avail = physmem_available ();
  total = physmem_total ();
  mem = MAX (avail, total / 8);
  fprintf (stderr, "default sort size: avail=%fM, total=%fM, mem=%fM\n", 
	avail/1024/1024, total/1024/1024, mem/1024/1024); 

  if (mem < size)
    size = mem;
  fprintf (stderr, "size is now: %dM\n", size/1024/1024);

  /* Here is the odd one out: If we've reduced the number too far,
     we'll increase it again here to the minimum value:
     MIN_SORT_SIZE */

  if (MIN_SORT_SIZE > size) 
    size = MIN_SORT_SIZE;

  fprintf (stderr, "returning: %dM\n", MAX (size, MIN_SORT_SIZE)/ 1024/1024);
  /* Use no less than the minimum.  */
  return size;
}


	Roger. 

-- 
** R.E.Wolff <at> BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.

Message #17 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Cc: Paul Eggert <eggert <at> cs.ucla.edu>, 10877 <at> debbugs.gnu.org
Subject: Re: bug#10877: Wimpy external files.
Date: Sat, 25 Feb 2012 14:59:21 +0000

A general note on this is to be wary of cache levels.
It may be more efficient to sort in chunks of the
cache level of the machine rather than as large
a chunk as possible.

Some very quick testing here (a while ago),
shows -S2M -T/dev/shm was as fast or faster than
big buffers, as well as being "nicer" to the rest
of the system.

cheers,
Pádraig.

p.s. ensure MALLOC_PERTURB_ is unset when benchmarking sort

Message #20 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Cc: 10877 <at> debbugs.gnu.org
Subject: Re: bug#10877: Wimpy external files.
Date: Sat, 25 Feb 2012 10:41:05 -0800

On 02/25/2012 04:56 AM, Rogier Wolff wrote:

> there is a logic error in the code that determines the
> maximum memory to use: You said it was supposed to use 1/8th of total
> memory. However it then takes another factor of two "margin".

Thanks for catching that.  I installed a fix (patch at end
of this message).

> I don't think that any guessing should be done if we cannot determine
> the filesize. In that case we have great heuristics to come up with a
> reasonable buffer size without the filesize.

A problem with that idea is, suppose we have many
independent 'sort' invocations running at at the same time,
as part of a shell pipeline say?  If they each grab 1/8 of
physical RAM, merely because they want to sort piped data of
a few bytes, they may exhaust swap space.

Perhaps we can improve the heuristics for pipes, but I hope
you can see why I'm a bit leery of a heuristic that says
"if the input is from a pipe, pretend it's from a file of
infinite size".

From 28197ef851af8f7e4f5f98f4433090cbbd63fbac Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Sat, 25 Feb 2012 10:32:52 -0800
Subject: [PATCH] sort: default to physmem/8, not physmem/16

* src/sort.c (default_sort_size): Don't divide advice by 2.
Just divide the hard limits by 2.  This matches the comments.
Reported by Rogier Wolff in http://bugs.gnu.org/10877
---
 src/sort.c |   14 +++++++-------
 1 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 6875a6a..60ff415 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -1414,13 +1414,9 @@ default_sort_size (void)
   struct rlimit rlimit;
 
   /* Let SIZE be MEM, but no more than the maximum object size or
-     system resource limits.  Avoid the MIN macro here, as it is not
-     quite right when only one argument is floating point.  Don't
-     bother to check for values like RLIM_INFINITY since in practice
-     they are not much less than SIZE_MAX.  */
+     system resource limits.  Don't bother to check for values like
+     RLIM_INFINITY since in practice they are not much less than SIZE_MAX.  */
   size_t size = SIZE_MAX;
-  if (mem < size)
-    size = mem;
   if (getrlimit (RLIMIT_DATA, &rlimit) == 0 && rlimit.rlim_cur < size)
     size = rlimit.rlim_cur;
 #ifdef RLIMIT_AS
@@ -1439,7 +1435,11 @@ default_sort_size (void)
     size = rlimit.rlim_cur / 16 * 15;
 #endif
 
-  /* Use no less than the minimum.  */
+  /* Return the minimum of MEM and SIZE, but no less than
+     MIN_SORT_SIZE.  Avoid the MIN macro here, as it is not quite
+     right when only one argument is floating point.  */
+  if (mem < size)
+    size = mem;
   return MAX (size, MIN_SORT_SIZE);
 }
 
-- 
1.7.6.5

Message #23 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Pádraig Brady <P <at> draigBrady.com>
Cc: 10877 <at> debbugs.gnu.org, Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Subject: Re: bug#10877: Wimpy external files.
Date: Sat, 25 Feb 2012 10:41:52 -0800

On 02/25/2012 06:59 AM, Pádraig Brady wrote:
> Some very quick testing here (a while ago),
> shows -S2M -T/dev/shm was as fast or faster than
> big buffers, as well as being "nicer" to the rest
> of the system.

I think this is a great idea for improving the
performance of 'sort' in the future.  It should
work particularly well with multithreaded sort
if we can assume that different cores have different
caches.  Admittedly getting at this info portably
may be a pain.  But perhaps I could assign that
to my students next quarter....

Message #26 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
To: Pádraig Brady <P <at> draigBrady.com>
Cc: Paul Eggert <eggert <at> cs.ucla.edu>, 10877 <at> debbugs.gnu.org,
	Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Subject: Re: bug#10877: Wimpy external files.
Date: Sun, 26 Feb 2012 07:53:11 +0100

On Sat, Feb 25, 2012 at 02:59:21PM +0000, Pádraig Brady wrote:
> Some very quick testing here (a while ago), shows -S2M -T/dev/shm
> was as fast or faster than big buffers, as well as being "nicer" to
> the rest of the system.

If that is the case, I expect it is still way faster to sort chunks of
the processor cache size, and then merge them in memory before writing
out chunks of a gigabyte (in my case with 8G RAM) to disk.

On the other hand. I'm not sure how efficient the 500-way merge is
going to be.

	Roger. 

-- 
** R.E.Wolff <at> BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.

Message #29 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 10877 <at> debbugs.gnu.org, Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Subject: Re: bug#10877: Wimpy external files.
Date: Sun, 26 Feb 2012 08:14:51 +0100

On Sat, Feb 25, 2012 at 10:41:05AM -0800, Paul Eggert wrote:
> A problem with that idea is, suppose we have many independent 'sort'
> invocations running at at the same time, as part of a shell pipeline
> say?  If they each grab 1/8 of physical RAM, merely because they
> want to sort piped data of a few bytes, they may exhaust swap space.

Two things. 

First: Many modern operating systems do "lazy" allocation. With 8G RAM
+ 8G SWAP you can have hundreds of apps each allocating a gigabyte, as
long as they don't all use that gigabyte. 

Second: If you're afraid for a lone operating system that DOES show
this problem, then a slight change in the codebase might be in order
for "unknown sort size". Then the "1/8th of memory" becomes an upper
bound and the buffer should be dynamically expanded. If you do not
have to "move" the data from the old buffer to a new buffer you can
just allocate a 2x larger buffer each time you reach the limit (but
are below the upper bound). If you DO have the expense of having to 
move all the data up to that point, I would suggest allocating a
4x larger buffer up to the upper bound. 

	Roger. 

-- 
** R.E.Wolff <at> BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.

Message #32 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
Cc: 10877 <at> debbugs.gnu.org
Subject: Re: bug#10877: Wimpy external files.
Date: Sat, 25 Feb 2012 23:26:01 -0800

On 02/25/2012 11:14 PM, Rogier Wolff wrote:

> Many modern operating systems do "lazy" allocation.

Sure, that's an old trick.  But this has its own problems:
it can mean a process *thinks* it has memory allocated, but it
doesn't *really* have the memory; which means when it tries to
actually *use* its memory it can get killed.  This is not a direction
we want 'sort' to head.

> a slight change in the codebase might be in order
> for "unknown sort size".

Sorry, I didn't follow the rest of that comment.  Perhaps you
could suggest a patch?  That might explain things better.
"diff -u" format is typically best.

Message #35 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Rogier Wolff <R.E.Wolff <at> BitWizard.nl>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 10877 <at> debbugs.gnu.org
Subject: Re: bug#10877: Wimpy external files.
Date: Sun, 26 Feb 2012 21:18:25 +0100

On Sat, Feb 25, 2012 at 11:26:01PM -0800, Paul Eggert wrote:
> On 02/25/2012 11:14 PM, Rogier Wolff wrote:
> 
> > Many modern operating systems do "lazy" allocation.
> 
> Sure, that's an old trick.  But this has its own problems:
> it can mean a process *thinks* it has memory allocated, but it
> doesn't *really* have the memory; which means when it tries to
> actually *use* its memory it can get killed.  This is not a direction
> we want 'sort' to head.

Hmm. Ok. 

> > a slight change in the codebase might be in order
> > for "unknown sort size".
> 
> Sorry, I didn't follow the rest of that comment.  Perhaps you
> could suggest a patch?  That might explain things better.
> "diff -u" format is typically best.

This one is more work than 10 minutes. Before I put in the effort I
would like to know if this is something that stands a chance...

Maybe some peudocode helps explain:

Currently there is a 

    bufsize = .... 
    buffer = malloc (bufsize); 

and then during the sorting something like: 

    if (data_in_buffer + new_data_len > bufsize) {
       write_data_from buffer (); 
    }

I propose to make that: 

    bufsize = .... ; // this returns a negative number to indicate it is a 
                     // wild guess, but an upper limit. 

    if (bufsize < 0) {
        curbufsize = MINBUFSIZE; 
	bufsize = -bufsize;
    } else {
	curbufsize = bufsize;
    }
    buffer = malloc (curbufsize); 

and then during the sorting: 

    if (data_in_buffer + new_data_len > curbufsize) {
       curbufsize *= 2; 
       if (curbufsize > bufsize) curbufsize = bufsize; 
       buffer = realloc (buffer, curbufsize);
       if (data_in_buffer + new_data_len > curbufsize) {
          write_data_from buffer (); 
       }
       write_data_from buffer (); 
    }

i.e. we determine an upper limit at "guessing time", and increase the
memory buffer up to that limit when the small default buffer ends up
being too small.

	Roger.

-- 
** R.E.Wolff <at> BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.

Message #40 received at 10877 <at> debbugs.gnu.org (full text, mbox):

From: Assaf Gordon <assafgordon <at> gmail.com>
Cc: 10877 <at> debbugs.gnu.org
Subject: Re: bug#10877: [sort] too eager to use temp files (WAS: Wimpy
 external files)
Date: Mon, 15 Oct 2018 10:12:34 -0600

tags 10877 fixed
close 10877
stop

(triaging old bugs)

The original issue reported in this bug was fixed here:

https://git.savannah.gnu.org/cgit/coreutils.git/commit/?id=a507ed6ede5064b8f15c979e54e6de3bb478d73e

Additional issues regarding sort/memory/temp files optimiazations
have not been touched upon in 6 years.

I'm closing this bug as "fixed".
If there is interest, discussion can continue by replying to this thread.

regards,
 - assaf

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.