Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #21836

Re: Breakthrough

Show key headers only | View raw

On 06/ 4/12 11:38 PM, jacob navia wrote:
> Hi
>
> In a recent discussion ("Open letter to Ian Collins") we found out that
> the main problem in the C containers library was the time taken by the
> Sort function.
>
> The reasons for that is that it was a general sort function calling a
> general comparison function that uses memcmp...
>
> The first step to improve performance was to write data type specific
> functions using a data type generic file. As a bonus, we get compile
> time checking and better syntax.
>
> Still, the generic sort function was taking a lot of time.
>
> I have written then a data type generic quick sort function that
> receives as a parameter a macro that is used to compare two elements.
> This vastly improves performance.
>
> The times are:
>
> Generic sort function without any specialized heap
> (using malloc)
> real	0m17.029s
> user	0m16.654s
> sys	0m0.368s
>
> Generic sort function using a specialized heap
> (reduces the malloc overhead)
> real	0m11.759s
> user	0m11.500s
> sys	0m0.252s
>
> "Templated" sort function using a macro parameter
> (reduces comparisons to a simple expression)
> real	0m6.453s
> user	0m6.165s
> sys	0m0.281s
>
> The expression used to compare two list elements is:
> #define COMPARE_EXPRESSION(A, B) \
>       ((*B)->Data>  (*A)->Data ? -1 : (*B)->Data != (*A)->Data)
>
> I thank Pete for that proposal, I wouldn't have come to it
> alone :-)
>
> I would like to have the corresponding C++ times but I fear that
> if I write it it would be unfair since I am not a C++ wizard...

I don't have the original code to had, but looking back at the original 
thread, the C++ list sort was 5x faster, so I guess from your numbers it 
is now 2-3 times faster.

-- 
Ian Collins

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 13:38 +0200
  Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 14:20 +0200
    Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-04 15:32 +0000
      Re: Breakthrough Ike Naar <ike@iceland.freeshell.org> - 2012-06-04 15:44 +0000
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 18:03 +0200
          Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:23 +1200
            Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:31 +0200
              Re: Breakthrough Luca Risolia <luca.risolia@studio.unibo.it> - 2012-06-05 01:43 +0200
                Re: Breakthrough Martin Shobe <martin.shobe@yahoo.com> - 2012-06-05 00:26 +0000
      Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 17:47 +0200
        Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-05 05:36 +0000
      Re: Breakthrough Paul <nospam@needed.com> - 2012-06-04 12:32 -0400
      Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 21:44 +0200
        Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 22:01 +0200
          Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 22:42 +0200
            Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:16 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:47 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 03:34 +0200
      Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-06 17:28 -0700
  Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 17:30 +0100
    Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 19:30 +0200
      Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 19:18 +0100
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 20:50 +0200
          Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-05 00:31 +0100
  Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-04 17:23 -0400
    Re: Breakthrough Noob <root@localhost> - 2012-06-05 09:10 +0200
      Re: Breakthrough Ike Naar <ike@sverige.freeshell.org> - 2012-06-05 08:03 +0000
      Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 00:20 -0400
        Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 00:06 -0500
          Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 09:10 -0400
            Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 09:23 -0500
              Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 19:49 -0400
                Re: Breakthrough Willem <willem@toad.stack.nl> - 2012-06-07 15:10 +0000
                Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-08 01:37 +0200
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 09:55 -0400
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 21:26 -0400
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-09 23:49 -0400
                Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-11 06:50 -0700
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-11 22:36 -0400
  Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:02 +1200
    Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:26 +0200

csiph-web