Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Breakthrough |
| Date | 2012-06-05 10:02 +1200 |
| Message-ID | <a34pjgFu5cU4@mid.individual.net> (permalink) |
| References | <jqi6o4$gqf$1@speranza.aioe.org> |
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
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