Re: [patch #3596] Sort directories before files in "ls"

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Francesco Montorsi on 12/22/2005 1:41 AM:
>>
>> EVIL.  You are calling qsort twice for every element (once to put
>> directories first, then twice again on the subsets).  This is twice as
>> slow as just writing a proper sort function that does everything all in
>> one comparison, so that you only call qsort once.
> 
> however if we want to make a single qsort call, then we'll need to
> declare a lot of new functions which merge previous tests with the
> groupdir test:
> 
> static int groupdir_compare_name (V a, V b)
> static int groupdir_compstr_name (V a, V b)
> static int groupdir_rev_cmp_name (V a, V b)
> static int groupdir_rev_str_name (V a, V b)
> 
> static int groupdir_compare_extension (V a, V b)
> static int groupdir_compstr_extension (V a, V b)
> static int groupdir_rev_cmp_extension (V a, V b)
> static int groupdir_rev_str_extension (V a, V b)
> 
> ...
> 
> 
> is it right ?

Yes, that was the approach I was thinking of.  Notice that some #define
magic may make the job easier, but I still think that reducing the number
of calls to qsort is more efficient than calling it multiple times.

> Won't that clutter the source file ?

No - we already have 2^2 variants per sort (based on strcoll/strcmp and
reverse/normal), adding --sort-directories-first (or whatever name others
like) would make it eight variants per sort, but qsort really does need an
entry point for every possible sort if you plan on calling qsort only
once.  I don't consider that cluttering the source file.  You really DO
have 3 orthogonal factors into sort order, leading to 2^3 entry points per
- --sort type to cover all the options.

Another approach would be adding a global variable that the sort functions
check on entry, but I would discourage that since it breaks the reentrancy
that currently exists in the sort functions, and since it would penalize
the normal case because every comparison would be checking the global
variable.

Something else to consider.  Maybe it is worth refactoring sort_files() a
bit.  Currently, it consists of nested switch statements that break into
lots of ?: conditionals.  Perhaps you can find a slick way to make an
array of function pointers, and then just index into the array based on
strcoll/strcmp, normal/reverse, and mixed/dirs-first to get the right
function pointer rather than going through lots of ?: conditionals.  I
don't know how that would look or if it would be any more or less
efficient, but I thought I would throw the idea out.

- --
Life is short - so eat dessert first!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFDqqhO84KuGfSFAYARAkoZAJ0RdQX11POofcxoIHSHaytQRZLGBACeKjFq
2bRJV++ANI46ocV46clpjoE=
=dJxN
-----END PGP SIGNATURE-----