Re: sort --random-sort

[Frederik Eaton]

On Wed, Nov 30, 2005 at 11:55:29AM +0100, Jim Meyering wrote:
> Frederik Eaton <address@hidden> wrote:
> > On Tue, Nov 29, 2005 at 07:31:45AM +0100, Jim Meyering wrote:
> >> Frederik Eaton <address@hidden> wrote:
> >> >> Maybe we need an option to trade off speed for quality,
> >> >> if it makes such a big difference.
> >> >
> >> > Hmm. Maybe there will be a difference. Well, why don't I make
> >> > ISAAC_LOG or ISAAC_WORDS part of isaac_state so that shred and sort
> >> > can use different values? I don't think it will be important for
> >> > 'sort' to use a very strong hash, since crackers only have the order
> >> > of the hash values to go by, and not the values themselves.
> >>
> >> This seems like a very good point.
> >> How about having this in rand-isaac.h:
> >>
> >> #ifndef ISAAC_LOG
> >> # define ISAAC_LOG 8
> >> #endif
> >>
> >> then define ISAAC_LOG to 3 just before including it from sort.c?
> >
> > Then I would also have to include rand-isaac.c in sort.c, since
> > rand-isaac.c itself includes rand-isaac.h, and is normally compiled
> > separately. What's wrong with making it a parameter of the state
> > structure?
> 
> If it's compiled separately with a variable state array size,
> then the state array will have to be allocated from the heap and
> freed when done.  Or you could avoid using the heap at the expense
> of limiting the size to some fixed maximum.  That would make this
> code more like random(3).
> 
> It's probably not worth much more effort to make the code
> stand-alone, since we'll probably remove it from shred -- then
> sort will be the only client.  Considering that, it might be best
> to simply include the .c file.  Either approach is fine with me.

I decided to limit the size of isaac_state, but make the actual state
array size configurable at runtime. It wasn't immediately trivial to
include rand-isaac.c in sort.c and I figured this would be cleaner. 
Tell me if you like what I've done.

With these changes shred is about 0.007 slower. I fixed a bug in
sort.c as well. Either because of that or the ISAAC changes, random
sort is now about 70% slower than normal sort (vs. 50% for my Nov 26
patch).

Frederik

shred-isaac-split.patch
Description: Text document

sort-with-isaac.patch
Description: Text document

sort-with-param-isaac.patch
Description: Text document