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

Groups > comp.lang.c > #21381 > unrolled thread

Open letter to Ian Collins

Back to article view | Back to comp.lang.c

Contents

  Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 00:22 +0200
    Re: Open letter to Ian Collins Ike Naar <ike@sverige.freeshell.org> - 2012-05-26 22:36 +0000
      Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 01:13 +0200
        Re: Open letter to Ian Collins Barry Schwarz <schwarzb@dqel.com> - 2012-05-26 16:53 -0700
      Re: Open letter to Ian Collins Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-26 16:41 -0700
        Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-26 22:43 -0400
    Re: Open letter to Ian Collins Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-26 15:41 -0700
      Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 01:14 +0200
    Re: Open letter to Ian Collins MelissA <melis@a.com> - 2012-05-27 00:52 +0200
    Re: Open letter to Ian Collins Stephen Sprunk <stephen@sprunk.org> - 2012-05-26 20:40 -0500
      Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 09:32 +0200
        Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 07:18 -0400
    Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 14:24 +1200
      Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 10:36 +0100
        Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 22:33 +1200
          Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 12:25 +0100
            Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-28 07:17 +1200
        Re: Open letter to Ian Collins Ike Naar <ike@sverige.freeshell.org> - 2012-05-27 13:03 +0000
    Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 15:16 +1200
      Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 09:30 +0200
        Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 20:56 +1200
          Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 11:12 +0200
            Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 21:22 +1200
              Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 07:15 -0400
              Re: Open letter to Ian Collins Keith Thompson <kst-u@mib.org> - 2012-05-27 07:49 -0700
                Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 13:55 -0400
                  Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 22:24 +0200
                    Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 22:09 +0100
                      Re: Open letter to Ian Collins Keith Thompson <kst-u@mib.org> - 2012-05-27 14:33 -0700
                        Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 17:49 -0400
                    Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 17:31 -0400
                      Re: Open letter to Ian Collins Philip Lantz <prl@canterey.us> - 2012-05-28 01:38 -0700
                        Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-28 08:18 -0400
          Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 15:46 +0100
          Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-06-13 21:25 -0400
            Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-06-13 21:52 -0400
            Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-06-14 04:00 +0200
              Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-06-14 00:04 -0400
    Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 09:42 +0200
    Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-28 12:39 +0200
      Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-28 21:44 +0200
        Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-29 09:46 +0200
          Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 10:06 +0200
            Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 10:37 +0200
              Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 10:58 +0200
                Re: Open letter to Ian Collins "Joachim Schmitz" <nospam.jojo@schmitz-digital.de> - 2012-05-29 11:34 +0200
                Re: Open letter to Ian Collins Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-29 03:02 -0700
        Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 09:59 +0200
        Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 20:09 +0200
    Re: Open letter to Ian Collins "Sarah Wren" <swreb@ameritech.net> - 2012-05-29 01:40 -0600

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#21399

On 05/27/12 07:30 PM, jacob navia wrote:
> Le 27/05/12 05:16, Ian Collins a écrit :
>> On 05/27/12 10:22 AM, jacob navia wrote:
>>> Hi Ian
>>>
>>> In the c++ newsgroup you asked me for an example of the ccl performance
>>> It was something with building a huge list, then sorting it, if I
>>> remember correctly...
>>>
>>> I have built this example code:
>>>
>> <snip>
>>
>> I get a segv when I run the example. Running in dbx with access checking
>> enabled shows:
>
> I corrected that yesterday. When you asked me gthis example I was in the
> middle of a reorganization of heap.c. Look at the latest update

OK, I thought I had but I didn't notice wget saving the file as cc.zip.1 
rather than overwriting the version I downloaded earlier in the week.

Anyway I ran ran the code built with Sun Studio rather than gcc because 
it runs quite a bit faster.  As I expected, the big difference was in 
sorting:

ccl version:

To sort     85.6384S

C++ version (std::list.sort()):

To sort     18.7927S

Iteration was closer:

To access    2.80655S (ccl)
To access    1.82896S

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#21400

Le 27/05/12 10:56, Ian Collins a écrit :
> As I expected, the big difference was in sorting:
>
> ccl version:
>
> To sort     85.6384S
>
> C++ version (std::list.sort()):
>
> To sort     18.7927S

Yes. But I am not finished yet. I am writing a generic
qsort module that will avoid the function call overhead of
the current solution.

As it is now, qsort calls a user defined sort function, that makes a
memcmp of the data...

With the generic qsort function you would directly compare
the data (without function calls) by specifying a macro
for comparing your data. For integers it would be simply

a - b

what should put me on equal footing to C++.

 > Iteration was closer:

 > To access    2.80655S (ccl)
 > To access    1.82896S

This is because iterators have a function call overhead.
But this is surely not catastrophic: if after 10 million
iterations the difference is just  1 second... it is not
really bad.

[toc] | [prev] | [next] | [standalone]

#21401

On 05/27/12 09:12 PM, jacob navia wrote:
> Le 27/05/12 10:56, Ian Collins a écrit :
>> As I expected, the big difference was in sorting:
>>
>> ccl version:
>>
>> To sort     85.6384S
>>
>> C++ version (std::list.sort()):
>>
>> To sort     18.7927S
>
> Yes. But I am not finished yet. I am writing a generic
> qsort module that will avoid the function call overhead of
> the current solution.
>
> As it is now, qsort calls a user defined sort function, that makes a
> memcmp of the data...
>
> With the generic qsort function you would directly compare
> the data (without function calls) by specifying a macro
> for comparing your data. For integers it would be simply
>
> a - b

That will be interesting to see.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#21406

Ian Collins wrote:
> 
> On 05/27/12 09:12 PM, jacob navia wrote:
> > Le 27/05/12 10:56, Ian Collins a écrit :
> >> As I expected, the big difference was in sorting:
> >>
> >> ccl version:
> >>
> >> To sort     85.6384S
> >>
> >> C++ version (std::list.sort()):
> >>
> >> To sort     18.7927S
> >
> > Yes. But I am not finished yet. I am writing a generic
> > qsort module that will avoid the function call overhead of
> > the current solution.
> >
> > As it is now, qsort calls a user defined sort function, that makes a
> > memcmp of the data...
> >
> > With the generic qsort function you would directly compare
> > the data (without function calls) by specifying a macro
> > for comparing your data. For integers it would be simply
> >
> > a - b
> 
> That will be interesting to see.

For generic array sorting functions that I've written,
I've had to #define 3 macros.
One E_TYPE macro for the element type,
a GT(A, B) macro for "greater than" comparison
and a MOV(A, B) macro for copying an element.

The MOV(A, B) macro is always #defined as either 
    ((void)(*(A) = *(B)))
or
    ((void)memcpy((A), (B), sizeof *(A))
depending on whether or not the element is an array type.


/* BEGIN output from ia_sort.c */

Arrays of element type (int),
are being sorted into ascending order.

This is the original order of the test array:
7
8
6

Sorted by simple selection sort:
6
7
8

Sorted by stable insertionsort:
6
7
8


Arrays of element type (char [sizeof "seven"]),
are being sorted by string length.

This is the original order of the test array:
seven
eight
six

Sorted by simple selection sort:
six
eight
seven

Sorted by stable insertionsort:
six
seven
eight

/* END output from ia_sort.c */





/* BEGIN ia_sort.c */
/*
** ia_sort.c               shows how to
** sort an array of int and also how to
** sort an array of array of six char, 
** from within the same file,
** using sort functions with the e_type interface.
*/
#include "ia_init.h"

#include <stdio.h>
#include <string.h>

#define NMEMB(A)    (sizeof (A) / sizeof *(A))

int main(void)
{
    size_t sort, element;
    char *description[] = {
        {"This is the original order of the test array:"},
        {"Sorted by simple selection sort:"},
        {"Sorted by stable insertionsort:"}
    };
    const int integer[] = {7,8,6};
    int arrayint[NMEMB(integer)];
    void (*sort_int[])(int *, size_t) = {
        no_sorti, 
          ssorti, 
         sisorti, 
    };
    const char string[][sizeof "seven"] = {"seven","eight","six"};
    char arraychar[NMEMB(string)][NMEMB(*string)];
    void (*sort_char[])(char (*)[NMEMB(*string)], size_t) = {
        no_sorta, 
          ssorta, 
         sisorta, 
    };
    
    puts("/* BEGIN output from ia_sort.c */");
    puts("\nArrays of element type (int),\n"
        "are being sorted into ascending order.\n");
    for (sort = 0; sort != NMEMB(sort_int); ++sort) {
        memcpy(arrayint, integer, sizeof arrayint);
        sort_int[sort](arrayint, NMEMB(arrayint));
        puts(description[sort]);
        for (element = 0; element != NMEMB(arrayint); ++element) {
            printf("%d\n", arrayint[element]);
        }
        putchar('\n');
    }
    puts("\nArrays of element type (char [sizeof \"seven\"]),\n"
         "are being sorted by string length.\n");
    for (sort = 0; sort != NMEMB(sort_char); ++sort) {
        memcpy(arraychar, string, sizeof arraychar);
        sort_char[sort](arraychar, NMEMB(arraychar));
        puts(description[sort]);
        for (element = 0; element != NMEMB(arraychar); ++element) {
            printf("%s\n", arraychar[element]);
        }
        putchar('\n');
    }
    puts("/* END output from ia_sort.c */");
    return 0;
}

/* END ia_sort.c */


/* BEGIN ia_init.h */

#ifndef H_IA_INIT_H
#define H_IA_INIT_H

#include <stddef.h>

void no_sorti(int *array, size_t nmemb);
void   ssorti(int *array, size_t nmemb);
void  sisorti(int *array, size_t nmemb);

void no_sorta(char (*array)[sizeof"seven"], size_t nmemb);
void   ssorta(char (*array)[sizeof"seven"], size_t nmemb);
void  sisorta(char (*array)[sizeof"seven"], size_t nmemb);

#endif

/* END ia_init.h */


/* BEGIN ia_init.c */

#include "ia_init.h"

#include <string.h>

#define SWAP(N, A, B, T)                        \
(MOV##N((T), (A)), MOV##N((A), (B)), MOV##N((B), (T)))

#define SORT_INIT(N)                            \
typedef E_TYPE##N;                              \
void no_sort##N(e_type##N *array, size_t nmemb) \
{                                               \
    array, nmemb;                               \
}                                               \
void ssort##N(e_type##N *array, size_t nmemb)   \
{                                               \
    e_type##N *first, *middle, temp;            \
    size_t counter;                             \
                                                \
    while (nmemb-- > 1) {                       \
        first = middle = array + 1;             \
        counter = nmemb;                        \
        while (--counter != 0) {                \
            ++middle;                           \
            if (GT##N(first, middle)) {         \
                first = middle;                 \
            }                                   \
        }                                       \
        if (GT##N(array, first)) {              \
            SWAP(N, array, first, &temp);       \
        }                                       \
        ++array;                                \
    }                                           \
}                                               \
void sisort##N(e_type##N *array, size_t nmemb)  \
{                                               \
    e_type##N *base, *low, *high, temp;         \
                                                \
    if (nmemb-- > 1) {                          \
        base = array;                           \
        do {                                    \
            low = array++;                      \
            if (GT##N(low, array)) {            \
                high = array;                   \
                MOV##N(&temp, high);            \
                do {                            \
                    MOV##N(high, low);          \
                    if (--high == base) {       \
                        break;                  \
                    }                           \
                    --low;                      \
                } while (GT##N(low, &temp));    \
                MOV##N(high, &temp);            \
            }                                   \
        } while (--nmemb != 0);                 \
    }                                           \
}

#define E_TYPEi     int e_typei
#define MOVi(A, B)  ((void)(*(A) = *(B)))
#define  GTi(A, B)  (*(A) > *(B))

#define E_TYPEa     char e_typea[sizeof "seven"]
#define MOVa(A, B)  ((void)memcpy((A), (B), sizeof *(A)))
#define  GTa(A, B)  (strlen(*(A)) > strlen(*(B)))

SORT_INIT(i)
SORT_INIT(a)

/* END ia_init.c */



-- 
pete

[toc] | [prev] | [next] | [standalone]

#21414

Ian Collins <ian-news@hotmail.com> writes:
> On 05/27/12 09:12 PM, jacob navia wrote:
[...]
>> With the generic qsort function you would directly compare
>> the data (without function calls) by specifying a macro
>> for comparing your data. For integers it would be simply
>>
>> a - b
>
> That will be interesting to see.

Especially for values like a==INT_MIN, b==INT_MAX.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#21417

Keith Thompson wrote:
> 
> Ian Collins <ian-news@hotmail.com> writes:
> > On 05/27/12 09:12 PM, jacob navia wrote:
> [...]
> >> With the generic qsort function you would directly compare
> >> the data (without function calls) by specifying a macro
> >> for comparing your data. For integers it would be simply
> >>
> >> a - b
> >
> > That will be interesting to see.
> 
> Especially for values like a==INT_MIN, b==INT_MAX.

I think there's about a zillion combinations of (a) and (b), 
where (a - b) has problems.

If (b) is negative, 
then (a - b) will be undefined whenever (a > b + INT_MAX).

If (b) is positive
then (a - b) will be undefined whenever (a < b + INT_MIN).

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21426

Le 27/05/12 19:55, pete a écrit :
> I think there's about a zillion combinations of (a) and (b),
> where (a - b) has problems.

Sure.

You want to say then that it is not a good idea in C to write

a - b

??

If you think that overflow could be a problem in a comparison you can
write something more complicated, expressions can be of any length, it
is only important that they be consequent.

You can of course test for overflow, and for any other conditions you
wish. If your integers are 32 bit you can force them into 64 bits for
doing the comparisons, for instance

[toc] | [prev] | [next] | [standalone]

#21431

"jacob navia" <jacob@spamsink.net> wrote in message 
news:jpu2h5$16r$1@speranza.aioe.org...
> Le 27/05/12 19:55, pete a écrit :
>> I think there's about a zillion combinations of (a) and (b),
>> where (a - b) has problems.
>
> Sure.
>
> You want to say then that it is not a good idea in C to write
>
> a - b
>
> ??
>
> If you think that overflow could be a problem in a comparison you can
> write something more complicated, expressions can be of any length, it
> is only important that they be consequent.

Maybe he means there might be more problems using:

 (a-b<=0)

than just using:

 (a<=b)

for example. Especially when a and b are unsigned. (Assuming the way 
comparisons will be done is along the lines of that former expression.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#21434

"BartC" <bc@freeuk.com> writes:
> "jacob navia" <jacob@spamsink.net> wrote in message 
> news:jpu2h5$16r$1@speranza.aioe.org...
>> Le 27/05/12 19:55, pete a écrit :
>>> I think there's about a zillion combinations of (a) and (b),
>>> where (a - b) has problems.
>>
>> Sure.
>>
>> You want to say then that it is not a good idea in C to write
>>
>> a - b
>>
>> ??
>>
>> If you think that overflow could be a problem in a comparison you can
>> write something more complicated, expressions can be of any length, it
>> is only important that they be consequent.
>
> Maybe he means there might be more problems using:
>
>  (a-b<=0)
>
> than just using:
>
>  (a<=b)
>
> for example. Especially when a and b are unsigned. (Assuming the way 
> comparisons will be done is along the lines of that former expression.)

My point is simply that "a - b" is not a reliable way to *compare*
two arbitrary integer values.  Using a wider type is not a general
solution.

If you *don't* think that overflow could be a problem in a
comparison, then you've probably missed something.

The language doesn't have a built-in 3-way comparison operator,
but it does have < and >.  Just use them.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#21437

Keith Thompson wrote:
> 
> "BartC" <bc@freeuk.com> writes:
> > "jacob navia" <jacob@spamsink.net> wrote in message
> > news:jpu2h5$16r$1@speranza.aioe.org...
> >> Le 27/05/12 19:55, pete a écrit :
> >>> I think there's about a zillion combinations of (a) and (b),
> >>> where (a - b) has problems.
> >>
> >> Sure.
> >>
> >> You want to say then that it is not a good idea in C to write
> >>
> >> a - b
> >>
> >> ??
> >>
> >> If you think that overflow could be a problem in a comparison you can
> >> write something more complicated, expressions can be of any length, it
> >> is only important that they be consequent.
> >
> > Maybe he means there might be more problems using:
> >
> >  (a-b<=0)
> >
> > than just using:
> >
> >  (a<=b)
> >
> > for example. Especially when a and b are unsigned. (Assuming the way
> > comparisons will be done is along the lines of that former expression.)
> 
> My point is simply that "a - b" is not a reliable way to *compare*
> two arbitrary integer values.  Using a wider type is not a general
> solution.
> 
> If you *don't* think that overflow could be a problem in a
> comparison, then you've probably missed something.
> 
> The language doesn't have a built-in 3-way comparison operator,
> but it does have < and >.  Just use them.

My prefered 3-way, to compare 2 integers, is

#define COMPAR(A, B) (B > A ? -1 : B != A)

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21433

jacob navia wrote:
> 
> Le 27/05/12 19:55, pete a écrit :
> > I think there's about a zillion combinations of (a) and (b),
> > where (a - b) has problems.
> 
> Sure.
> 
> You want to say then that it is not a good idea in C to write
> 
> a - b
> 
> ??

What I want to say, is that what you wrote:

    "With the generic qsort function 
     you would directly compare the data
     (without function calls) by specifying a macro
     for comparing your data. 
     For integers it would be simply

     a - b"

doesn't correspond to any notion 
of what "generic qsort function" could possibly mean.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21454

pete wrote:
> What I want to say, is that what you wrote:
> 
>     "With the generic qsort function 
>      you would directly compare the data
>      (without function calls) by specifying a macro
>      for comparing your data. 
>      For integers it would be simply
> 
>      a - b"
> 
> doesn't correspond to any notion 
> of what "generic qsort function" could possibly mean.

You misunderstood. The qsort function is generic. The comparison macro 
isn't generic, it is specific to the data being sorted. "a - b" could be 
a valid comparison macro for some data sets where the range of the data 
is known. However, Jacob did overgeneralize a bit when he said that it 
would be appropriate "for integers", without further qualification.

[toc] | [prev] | [next] | [standalone]

#21466

Philip Lantz wrote:
> 
> pete wrote:
> > What I want to say, is that what you wrote:
> >
> >     "With the generic qsort function
> >      you would directly compare the data
> >      (without function calls) by specifying a macro
> >      for comparing your data.
> >      For integers it would be simply
> >
> >      a - b"
> >
> > doesn't correspond to any notion
> > of what "generic qsort function" could possibly mean.
> 
> You misunderstood. The qsort function is generic.
> The comparison macro isn't generic,
> it is specific to the data being sorted.
> "a - b" could be a valid comparison macro
> for some data sets where the range of the data is known.
> However, Jacob did overgeneralize a bit when he said that it
> would be appropriate "for integers", without further qualification.

Thank you.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21413

"Ian Collins" <ian-news@hotmail.com> wrote in message 
news:a2e8hgF7faU3@mid.individual.net...


> ccl version:
>
> To sort     85.6384S
>
> C++ version (std::list.sort()):
>
> To sort     18.7927S
>
> Iteration was closer:
>
> To access    2.80655S (ccl)
> To access    1.82896S

What does iteration measure, in terms of the example program? Just the same 
thing, but without the sort?

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#22239

Ian Collins wrote:
> 
> On 05/27/12 07:30 PM, jacob navia wrote:
> > Le 27/05/12 05:16, Ian Collins a écrit :
> >> On 05/27/12 10:22 AM, jacob navia wrote:
> >>> Hi Ian
> >>>
> >>> In the c++ newsgroup you asked me
> >>> for an example of the ccl performance
> >>> It was something with building a huge list, then sorting it, if I
> >>> remember correctly...
> >>>
> >>> I have built this example code:
> >>>
> >> <snip>
> >>
> >> I get a segv when I run the example.
> >> Running in dbx with access checking
> >> enabled shows:
> >
> > I corrected that yesterday.
> > When you asked me gthis example I was in the
> > middle of a reorganization of heap.c. Look at the latest update
> 
> OK,
> I thought I had but I didn't notice wget saving the file as cc.zip.1
> rather than overwriting the version I downloaded earlier in the week.
> 
> Anyway I ran ran the code
> built with Sun Studio rather than gcc because
> it runs quite a bit faster.  As I expected, the big difference was in
> sorting:
> 
> ccl version:
> 
> To sort     85.6384S
> 
> C++ version (std::list.sort()):
> 
> To sort     18.7927S
> 
> Iteration was closer:
> 
> To access    2.80655S (ccl)
> To access    1.82896S

/*
** Would you please run this program
** and let me know what the output is?
** I'm of the opinion that the QSORT function
** which is currently in listgen.c, at
** http://code.google.com/p/ccl/downloads/detail?name=ccl.zip&can=2&q= 
** has approximately zero chance of correctly sorting
** a data set of as many as 10000000 psuedorandom keys.
*/
#include <stdlib.h>

#include "containers.h"
#include "intlist.h"

#define N 10000000

int 
main(void)
{
    intList *L1;
    size_t i;
    int d;
    long unsigned sum=0,newSum=0;
    Iterator *it;
    int *pint, last_pint;
    
    L1 = iintList.Create(sizeof(int));
    iintList.UseHeap(L1,NULL); // Use specialized Heap
    // Add N random numbers to the integer list
    for (i=0; i<N;i++) {
        d = rand();
        sum += d;
        iintList.Add(L1,d);
    }
    // Sort it
    iintList.Sort(L1);
    // Go through the sorted list using an iterator
    it = iintList.NewIterator(L1);
    i=0;
    pint = it->GetFirst(it);
    while (pint != NULL) {
        last_pint = *pint;
        newSum += last_pint;
        pint = it->GetNext(it);
        if (pint != NULL && last_pint > *pint) {
            puts("\n\nThe data is not sorted.\n\n");
            iintList.Finalize(L1);
            exit(EXIT_SUCCESS);
        }
    }
    // Verify that both sums are identical
    if (sum != newSum) {
        printf("Failed\n");
    } else {
        printf("Sum = %lu\n",sum);
    }
    // Destroy the list
    iintList.Finalize(L1);
    return 0;
}

-- 
pete

[toc] | [prev] | [next] | [standalone]

#22240

pete wrote:
> 
> Ian Collins wrote:
 
> /*
> ** Would you please run this program
> ** and let me know what the output is?
> ** I'm of the opinion that the QSORT function
> ** which is currently in listgen.c, at
> ** http://code.google.com/p/ccl/downloads/detail?name=ccl.zip&can=2&q=
> ** has approximately zero chance of correctly sorting
> ** a data set of as many as 10000000 psuedorandom keys.
> */
> #include <stdlib.h>
> 
> #include "containers.h"
> #include "intlist.h"
> 
> #define N 10000000
> 
> int
> main(void)
> {
>     intList *L1;
>     size_t i;
>     int d;
>     long unsigned sum=0,newSum=0;
>     Iterator *it;
>     int *pint, last_pint;
> 
>     L1 = iintList.Create(sizeof(int));
>     iintList.UseHeap(L1,NULL); // Use specialized Heap
>     // Add N random numbers to the integer list
>     for (i=0; i<N;i++) {
>         d = rand();
>         sum += d;
>         iintList.Add(L1,d);
>     }
>     // Sort it
>     iintList.Sort(L1);
>     // Go through the sorted list using an iterator
>     it = iintList.NewIterator(L1);
>     i=0;
>     pint = it->GetFirst(it);
>     while (pint != NULL) {
>         last_pint = *pint;
>         newSum += last_pint;
>         pint = it->GetNext(it);
>         if (pint != NULL && last_pint > *pint) {
>             puts("\n\nThe data is not sorted.\n\n");
>             iintList.Finalize(L1);
>             exit(EXIT_SUCCESS);
>         }
>     }
>     // Verify that both sums are identical
>     if (sum != newSum) {
>         printf("Failed\n");
>     } else {
>         printf("Sum = %lu\n",sum);
>     }
>     // Destroy the list
>     iintList.Finalize(L1);
>     return 0;
> }

After looking at it more closley, 
I think that I may have been wrong,
but please check it anyway.
Thank you.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#22241

Le 14/06/12 03:25, pete a écrit :
> Ian Collins wrote:
>>
>> On 05/27/12 07:30 PM, jacob navia wrote:
>>> Le 27/05/12 05:16, Ian Collins a écrit :
>>>> On 05/27/12 10:22 AM, jacob navia wrote:
>>>>> Hi Ian
>>>>>
>>>>> In the c++ newsgroup you asked me
>>>>> for an example of the ccl performance
>>>>> It was something with building a huge list, then sorting it, if I
>>>>> remember correctly...
>>>>>
>>>>> I have built this example code:
>>>>>
>>>> <snip>
>>>>
>>>> I get a segv when I run the example.
>>>> Running in dbx with access checking
>>>> enabled shows:
>>>
>>> I corrected that yesterday.
>>> When you asked me gthis example I was in the
>>> middle of a reorganization of heap.c. Look at the latest update
>>
>> OK,
>> I thought I had but I didn't notice wget saving the file as cc.zip.1
>> rather than overwriting the version I downloaded earlier in the week.
>>
>> Anyway I ran ran the code
>> built with Sun Studio rather than gcc because
>> it runs quite a bit faster.  As I expected, the big difference was in
>> sorting:
>>
>> ccl version:
>>
>> To sort     85.6384S
>>
>> C++ version (std::list.sort()):
>>
>> To sort     18.7927S
>>
>> Iteration was closer:
>>
>> To access    2.80655S (ccl)
>> To access    1.82896S
>
> /*
> ** Would you please run this program
> ** and let me know what the output is?
> ** I'm of the opinion that the QSORT function
> ** which is currently in listgen.c, at
> ** http://code.google.com/p/ccl/downloads/detail?name=ccl.zip&can=2&q=
> ** has approximately zero chance of correctly sorting
> ** a data set of as many as 10000000 psuedorandom keys.
> */
> #include<stdlib.h>
>
> #include "containers.h"
> #include "intlist.h"
>
> #define N 10000000
>
> int
> main(void)
> {
>      intList *L1;
>      size_t i;
>      int d;
>      long unsigned sum=0,newSum=0;
>      Iterator *it;
>      int *pint, last_pint;
>
>      L1 = iintList.Create(sizeof(int));
>      iintList.UseHeap(L1,NULL); // Use specialized Heap
>      // Add N random numbers to the integer list
>      for (i=0; i<N;i++) {
>          d = rand();
>          sum += d;
>          iintList.Add(L1,d);
>      }
>      // Sort it
>      iintList.Sort(L1);
>      // Go through the sorted list using an iterator
>      it = iintList.NewIterator(L1);
>      i=0;
>      pint = it->GetFirst(it);
>      while (pint != NULL) {
>          last_pint = *pint;
>          newSum += last_pint;
>          pint = it->GetNext(it);
>          if (pint != NULL&&  last_pint>  *pint) {
>              puts("\n\nThe data is not sorted.\n\n");
>              iintList.Finalize(L1);
>              exit(EXIT_SUCCESS);
>          }
>      }
>      // Verify that both sums are identical
>      if (sum != newSum) {
>          printf("Failed\n");
>      } else {
>          printf("Sum = %lu\n",sum);
>      }
>      // Destroy the list
>      iintList.Finalize(L1);
>      return 0;
> }
>

Hi Pete

The output is:
Sum = 10737818730605039

Maybe because I incorporated the changes you proposed to the quick sort
template after the last discussion.

You get another output? Have you tried with the latest sources?

Thanks for your help.

jacob

[toc] | [prev] | [next] | [standalone]

#22245

jacob navia wrote:
> 
> Le 14/06/12 03:25, pete a écrit :
> > Ian Collins wrote:
> >>

> > /*
> > ** Would you please run this program
> > ** and let me know what the output is?
> > ** I'm of the opinion that the QSORT function
> > ** which is currently in listgen.c, at
> > ** http://code.google.com/p/ccl/downloads/detail?name=ccl.zip&can=2&q=
> > ** has approximately zero chance of correctly sorting
> > ** a data set of as many as 10000000 psuedorandom keys.
> > */
> > #include<stdlib.h>
> >
> > #include "containers.h"
> > #include "intlist.h"
> >
> > #define N 10000000
> >
> > int
> > main(void)
> > {
> >      intList *L1;
> >      size_t i;
> >      int d;
> >      long unsigned sum=0,newSum=0;
> >      Iterator *it;
> >      int *pint, last_pint;
> >
> >      L1 = iintList.Create(sizeof(int));
> >      iintList.UseHeap(L1,NULL); // Use specialized Heap
> >      // Add N random numbers to the integer list
> >      for (i=0; i<N;i++) {
> >          d = rand();
> >          sum += d;
> >          iintList.Add(L1,d);
> >      }
> >      // Sort it
> >      iintList.Sort(L1);
> >      // Go through the sorted list using an iterator
> >      it = iintList.NewIterator(L1);
> >      i=0;
> >      pint = it->GetFirst(it);
> >      while (pint != NULL) {
> >          last_pint = *pint;
> >          newSum += last_pint;
> >          pint = it->GetNext(it);
> >          if (pint != NULL&&  last_pint>  *pint) {
> >              puts("\n\nThe data is not sorted.\n\n");
> >              iintList.Finalize(L1);
> >              exit(EXIT_SUCCESS);
> >          }
> >      }
> >      // Verify that both sums are identical
> >      if (sum != newSum) {
> >          printf("Failed\n");
> >      } else {
> >          printf("Sum = %lu\n",sum);
> >      }
> >      // Destroy the list
> >      iintList.Finalize(L1);
> >      return 0;
> > }
> >
> 
> Hi Pete
> 
> The output is:
> Sum = 10737818730605039
> 
> Maybe because I incorporated the
> changes you proposed to the quick sort
> template after the last discussion.
> 
> You get another output?

No. 
I misread the code.
Where I saw 
    swap(lo, higuy);
I mistakenly thought instead that it was
    swap(loguy, higuy);

> Have you tried with the latest sources?

No.
 
> Thanks for your help.

You're welcome 
and I'm sorry about the misunderstanding.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21397

Le 27/05/12 00:22, jacob navia a écrit :

[snip code]

Measuring the speed of the program, you can see that a big part of the
time is spent in malloc.

Without the line

iList.UseHeap(L1);

we obtain
real	0m16.842s
user	0m16.421s
sys	0m0.401s


but using a specialized heap we obtain
real	0m11.541s
user	0m11.253s
sys	0m0.253s

Problem is, a specialized heap (for objects of the same size)
is difficult to implement correctly. After several tentatives
I have decided that I would have

1) An array of block pointers that can be realloced to hold more
   if full.
2) Each of the positions of the pointers array points to a block of
    1000 objects. Those can't be realloced since they are passed
    to user programs
3) A bit map that marks which positions are free within the
    structure. It should contain
    Number of blocks * 1000 bits

When freeing a position I mark the corresponding bit as free
and put the object in the free list.

I am still not done with this.

jacob

[toc] | [prev] | [next] | [standalone]

#21460

"jacob navia" <jacob@spamsink.net> ha scritto nel messaggio
news:jprl29$ifd$1@speranza.aioe.org...
> Hi Ian
>
> In the c++ newsgroup you asked me for an example of the ccl performance
> It was something with building a huge list, then sorting it, if I remember
> correctly...
>
> I have built this example code:
>
> #include <stdlib.h>
> #include "containers.h"
> #define N 10000000
> int main(void)
> {
>         List *L1;
>         size_t i,d;
>         long long sum=0,newSum=0;
>         Iterator *it;
>         int *pint;
>
>         L1 = iList.Create(sizeof(int));


the size of the element of the struct is not enought
for descrive one type in C ...
the above could be ok for type dipend only by the size...

i think for 'descrive' the type object one has need
3 C functions at last: one constructor, one destructor
one copy function... :)
Buon Giorno

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web