Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Open letter to Ian Collins
101 views
Skip to first unread message
jacob navia
May 26, 2012, 6:22:01 PM5/26/12
to
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));
iList.UseHeap(L1,NULL);
for (i=0; i<N;i++) {
d = rand();
sum += d;
iList.Add(L1,&d);
}
iList.Sort(L1);
it = iList.NewIterator(L1);
for (pint = it->GetFirst(it); pint; pint = it->GetNext(it)) {
newSum += *pint;
}
if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);
iList.Finalize(L1);
}
This creates a list, then fills it with 10 million random integers,
then sorts it and verifies that all the data is still there by
accessing all elements of the list with an iterator.
Can you please send me an equivalent C++program?
Thanks
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));
iList.UseHeap(L1,NULL);
for (i=0; i<N;i++) {
d = rand();
sum += d;
iList.Add(L1,&d);
}
iList.Sort(L1);
it = iList.NewIterator(L1);
for (pint = it->GetFirst(it); pint; pint = it->GetNext(it)) {
newSum += *pint;
}
if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);
iList.Finalize(L1);
}
This creates a list, then fills it with 10 million random integers,
then sorts it and verifies that all the data is still there by
accessing all elements of the list with an iterator.
Can you please send me an equivalent C++program?
Thanks
Ike Naar
May 26, 2012, 6:36:29 PM5/26/12
to
On 2012-05-26, jacob navia <ja...@spamsink.net> 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:
>
> #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));
> iList.UseHeap(L1,NULL);
> for (i=0; i<N;i++) {
> d = rand();
> sum += d;
> iList.Add(L1,&d);
This seems dangerous. iList.Add expects a pointer to an
> 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));
> iList.UseHeap(L1,NULL);
> for (i=0; i<N;i++) {
> d = rand();
> sum += d;
> iList.Add(L1,&d);
int for the second argument, and it receives a pointer to
a size_t. What if int and size_t have different sizes?
Malcolm McLean
May 26, 2012, 6:41:04 PM5/26/12
to ja...@jspamsink.org
בתאריך יום שבת, 26 במאי 2012 23:22:01 UTC+1, מאת jacob navia:
> iList.Sort(L1);
> iList.Sort(L1);
> Can you please send me an equivalent C++program?
>
You very rarely want to sort a list of integers or other atomic type. Almost always you want to sort records based on a field, or on two fields, e.g. surname followed by intials, or you want to do somethign funny, like sorting strings alphabetically but putting embedded numbers in numeric order so that fred_99 comes before fred_100.
>
MelissA
May 26, 2012, 6:52:23 PM5/26/12
to
by value (doesn't change nodes order) is much faster than
standard stl list sort (which changes nodes order).
Also after sort that doesn't change nodes order, traversing
is much faster then after sort that does change nodes order.
That is of course if initial list nodes are consecutive.
Doesn't matter how much cache cpu has 512kb is enough
to show significant difference.
Greetings!
jacob navia
May 26, 2012, 7:13:37 PM5/26/12
to
Le 27/05/12 00:36, Ike Naar a écrit :
all.
The other way around would be dangerous: passing a pointer to int to a
size_t;
But strictly speaking you are right of course. Will change that.
> This seems dangerous. iList.Add expects a pointer to an
> int for the second argument, and it receives a pointer to
> a size_t. What if int and size_t have different sizes?
Well, the list software will read the lower sizeof(int) bytes, that's
> int for the second argument, and it receives a pointer to
> a size_t. What if int and size_t have different sizes?
all.
The other way around would be dangerous: passing a pointer to int to a
size_t;
But strictly speaking you are right of course. Will change that.
jacob navia
May 26, 2012, 7:14:49 PM5/26/12
to
Le 27/05/12 00:41, Malcolm McLean a écrit :
I know, it is just for comparing performance of ccl vs stl
Malcolm McLean
May 26, 2012, 7:41:13 PM5/26/12
to
בתאריך יום שבת, 26 במאי 2012 23:36:29 UTC+1, מאת Ike Naar:
>
> This seems dangerous. iList.Add expects a pointer to an
> int for the second argument, and it receives a pointer to
> a size_t. What if int and size_t have different sizes?
>
Yes, size_t is a menace. I've been saying that for a while. The problem is that programmers are unwilling to use it consistently. If you want an integer, you type int.
> This seems dangerous. iList.Add expects a pointer to an
> int for the second argument, and it receives a pointer to
> a size_t. What if int and size_t have different sizes?
>
Barry Schwarz
May 26, 2012, 7:53:41 PM5/26/12
to
On Sun, 27 May 2012 01:13:37 +0200, jacob navia <ja...@spamsink.net>
wrote:
>Le 27/05/12 00:36, Ike Naar a écrit :
>> This seems dangerous. iList.Add expects a pointer to an
>> int for the second argument, and it receives a pointer to
>> a size_t. What if int and size_t have different sizes?
>
>Well, the list software will read the lower sizeof(int) bytes, that's
>all.
And on a big-endian machine this will produce the correct value?
Not to mention the mandatory diagnostic during compilation.
>
>The other way around would be dangerous: passing a pointer to int to a
>size_t;
>
>But strictly speaking you are right of course. Will change that.
Even casually speaking.
--
Remove del for email
wrote:
>Le 27/05/12 00:36, Ike Naar a écrit :
>> This seems dangerous. iList.Add expects a pointer to an
>> int for the second argument, and it receives a pointer to
>> a size_t. What if int and size_t have different sizes?
>
>Well, the list software will read the lower sizeof(int) bytes, that's
>all.
Not to mention the mandatory diagnostic during compilation.
>
>The other way around would be dangerous: passing a pointer to int to a
>size_t;
>
>But strictly speaking you are right of course. Will change that.
--
Remove del for email
Stephen Sprunk
May 26, 2012, 9:40:04 PM5/26/12
to
On 26-May-12 17:22, 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...
Then shouldn't you have posted the response to "the c++ newsgroup"
> 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...
rather than comp.lang.c?
> [a bunch of C++ code]
Off-topic here.
S
--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking
Ian Collins
May 26, 2012, 10:24:24 PM5/26/12
to
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:
>
> #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;
All good code should have at least one beer reference!
> 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;
It be a lot easier to see what is what if these were declared on first use.
> L1 = iList.Create(sizeof(int));
> iList.UseHeap(L1,NULL);
> for (i=0; i<N;i++) {
> d = rand();
> sum += d;
> iList.Add(L1,&d);
> }
> iList.Sort(L1);
> it = iList.NewIterator(L1);
> for (pint = it->GetFirst(it); pint; pint = it->GetNext(it)) {
> newSum += *pint;
> }
> if (sum != newSum)
> printf("Failed\n");
> else printf("Sum = %lld\n",sum);
> iList.Finalize(L1);
> }
>
> This creates a list, then fills it with 10 million random integers,
> then sorts it and verifies that all the data is still there by
> accessing all elements of the list with an iterator.
>
> Can you please send me an equivalent C++program?
c.l.c++ thread you should have posted this in response to.
--
Ian Collins
pete
May 26, 2012, 10:43:33 PM5/26/12
to
was the best choice for either (i) or (d).
(i) was counting nodes in a list
and the standard definition of what (size_t) is supposed to be,
isn't related to how many nodes can be in a list.
I think I would have used the largest unsigned integer type for (i).
(d) was assigned the return value of rand(),
so (int) is the type that would first occur to me to use for (d).
Unsigned integer types would have been the first thing
to occur to me to use for the checksums.
And even though nobody wants to see it,
this is how I would have written a program like that in C:
http://www.mindspring.com/~pfilandr/C/lists_and_files/list_lib.h
http://www.mindspring.com/~pfilandr/C/lists_and_files/list_lib.c
http://www.mindspring.com/~pfilandr/C/lists_and_files/list_type.h
/* BEGIN new.c */
#include "list_lib.h"
#include <stdio.h>
#include <stdlib.h>
#define N 1000000
#define str(s) # s
#define xstr(s) str(s)
int int_comp(const void *a, const void *b);
int
main(void)
{
int d, *d_ptr;
long unsigned i;
unsigned old_checksum = 0;
unsigned new_checksum = 0;
list_type *head = NULL;
list_type *tail = NULL;
puts("/* BEGIN output new.c */\n\nN is " xstr(N) "\n");
for (i = 0; i != N; ++i) {
d = rand();
old_checksum += d;
tail = list_append(&head, tail, &d, sizeof d);
if (tail == NULL) {
puts("tail == NULL");
printf("list only contains %lu nodes,\n\n", i);
break;
}
}
tail = head = list_sort(head, int_comp);
while (tail != NULL) {
d_ptr = tail -> data;
d = *d_ptr;
new_checksum += d;
tail = tail -> next;
if (tail != NULL && int_comp(d_ptr, tail -> data) > 0) {
puts("list is out of order\n");
break;
}
}
list_free(head, free);
head = tail = NULL;
printf("old_checksum is %lu.\n", old_checksum);
printf("new_checksum is %lu.\n", new_checksum);
puts("\n/* END output new.c */");
return 0;
}
int
int_comp(const void *a, const void *b)
{
const int *const aa = a;
const int *const bb = b;
return *bb > *aa ? -1 : *bb != *aa;
}
/* END new.c */
--
pete
Ian Collins
May 26, 2012, 11:16:15 PM5/26/12
to
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>
>
> 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:
>
I get a segv when I run the example. Running in dbx with access
checking enabled shows:
Write to unallocated (wua):
Attempting to write 1 byte at address 0x8091d88
which is just past heap block of size 800 bytes at 0x8091a68
This block was allocated from:
newHeapObject<-NewLink<-Add_nd<-Add<-main
Location of error: heap.c, line 75, newHeapObject()
The offending code appears to be here in heap.c:
/* The array of block pointers is full. Allocate CHUNK_SIZE blocks
more */
siz = (l->BlockCount+CHUNK_SIZE)*sizeof(ListElement *);
result = l->Allocator->realloc(l->Heap,siz);
if (result == NULL) {
return NULL;
}
l->MemoryUsed+= siz;
l->Heap = (char **)result;
/* Position pointer at the start of the new area */
result += l->BlockCount*sizeof(ListElement *);
/* Zero the new pointers */
memset(result,0,siz);
It looks like you are allocating siz byes, incrementing part (half) way
through the bock then zeroing the next siz bytes.
--
Ian Collins
jacob navia
May 27, 2012, 3:30:11 AM5/27/12
to
Le 27/05/12 05:16, Ian Collins a écrit :
middle of a reorganization of heap.c. Look at the latest update
> 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
>> 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:
middle of a reorganization of heap.c. Look at the latest update
jacob navia
May 27, 2012, 3:32:17 AM5/27/12
to
Le 27/05/12 03:40, Stephen Sprunk a écrit :
It compiles with every C compiler you can choose...
Never mind, don't let facts disturb your beliefs.
>> [a bunch of C++ code]
Why is it C++?
It compiles with every C compiler you can choose...
Never mind, don't let facts disturb your beliefs.
jacob navia
May 27, 2012, 3:42:18 AM5/27/12
to
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
[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
Ian Collins
May 27, 2012, 4:56:16 AM5/27/12
to
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
jacob navia
May 27, 2012, 5:12:22 AM5/27/12
to
Le 27/05/12 10:56, Ian Collins a écrit :
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.
> 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
>
> ccl version:
>
> To sort 85.6384S
>
> C++ version (std::list.sort()):
>
> To sort 18.7927S
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
But this is surely not catastrophic: if after 10 million
iterations the difference is just 1 second... it is not
really bad.
Ian Collins
May 27, 2012, 5:22:00 AM5/27/12
to
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.
> 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
--
Ian Collins
BartC
May 27, 2012, 5:36:04 AM5/27/12
to
"Ian Collins" <ian-...@hotmail.com> wrote in message
news:a2dhip...@mid.individual.net...
> 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:
>>
>> #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;
>
> All good code should have at least one beer reference!
>
> It be a lot easier to see what is what if these were declared on first
> use.
As in, instead of reading a play which starts with a cast of characters,
>> 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;
>
> All good code should have at least one beer reference!
>
> It be a lot easier to see what is what if these were declared on first
> use.
they should be introduced whenever they first appear?
Suppose you're delving into a random scene, (or have an extract for use
elsewhere), and want to be reminded who a character is, you have to start
ploughing through from page one first until you encounter their first
mention?
And if you are editing the play, and the character's first appearance is
edited out, or is moved somewhere where it's no longer the first appearance;
how much work is it going to be to fix up declarations properly?
Getting back to C, wouldn't macros and enumerations (and file-scope
variables, external references, etc) also all benefit from being declared
where they are first used? (And what sort of mess would that make of any
program...).
Anyway I thought everyone used smart editors now, where you hover over a
name or something, and it tells you everything about it.
--
Bartc
Ian Collins
May 27, 2012, 6:33:07 AM5/27/12
to
> And if you are editing the play, and the character's first appearance is
> edited out, or is moved somewhere where it's no longer the first appearance;
> how much work is it going to be to fix up declarations properly?
> Getting back to C, wouldn't macros and enumerations (and file-scope
> variables, external references, etc) also all benefit from being declared
> where they are first used? (And what sort of mess would that make of any
> program...).
needed makes them shorter. Besides, how do you introduce a const other
that where it is initialised?
> Anyway I thought everyone used smart editors now, where you hover over a
> name or something, and it tells you everything about it.
--
Ian Collins
pete
May 27, 2012, 7:15:01 AM5/27/12
to
Ian Collins wrote:
>
> On 05/27/12 09:12 PM, jacob navia wrote:
> > Le 27/05/12 10:56, Ian Collins a �crit :
>
> On 05/27/12 09:12 PM, jacob navia wrote:
> >> 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,
> >>
> >> 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.
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
pete
May 27, 2012, 7:18:23 AM5/27/12
to
jacob navia wrote:
>
> Le 27/05/12 03:40, Stephen Sprunk a écrit :
> >> [a bunch of C++ code]
>
> Why is it C++?
He probably didn't know what "containers.h" was.
>
> Le 27/05/12 03:40, Stephen Sprunk a écrit :
> >> [a bunch of C++ code]
>
> Why is it C++?
> It compiles with every C compiler you can choose...
>
> Never mind, don't let facts disturb your beliefs.
pete
BartC
May 27, 2012, 7:25:42 AM5/27/12
to
"Ian Collins" <ian-...@hotmail.com> wrote in message
news:a2ee73...@mid.individual.net...
>>> It be a lot easier to see what is what if these were declared on first
>>> use.
>>
>> As in, instead of reading a play which starts with a cast of characters,
>> they should be introduced whenever they first appear?
>>
>> Suppose you're delving into a random scene, (or have an extract for use
>> elsewhere), and want to be reminded who a character is, you have to start
>> ploughing through from page one first until you encounter their first
>> mention?
>
> A function is more like a limerick than a play.
In that case I can't see it being a big imposition if the names were
>>> use.
>>
>> As in, instead of reading a play which starts with a cast of characters,
>> they should be introduced whenever they first appear?
>>
>> Suppose you're delving into a random scene, (or have an extract for use
>> elsewhere), and want to be reminded who a character is, you have to start
>> ploughing through from page one first until you encounter their first
>> mention?
>
> A function is more like a limerick than a play.
declared at the top of the function (ie. at the top of the screen if a
function is small). Then it gets the clutter out of the code. And all uses
of the name are identical (instead of one of them needing a declaration).
Although, it will make the function a bit longer..
>> Getting back to C, wouldn't macros and enumerations .... also
>> all benefit from being declared where they are first used?
> I would make them longer, unlike declaring variables when they are needed
> makes them shorter.
That's another thing; uses of i, j and k for loop indices is fairly
> makes them shorter.
standard. They probably will be ints, and the formality of having to declare
them can be kept out of the way instead of making for-loops even longer.
(Alternatively for-loop variables could be implicitly declared.)
> Besides, how do you introduce a const other that where it is initialised?
places, then it can also benefit from splitting declaration (and
initialisation) from it's use.
It gets more complicated when declarations in blocks are used (which
apparently have their own name spaces). But I've never used those, and if
functions are small as everyone says they should be, I can't see the need.
(Of course my point of view is from reading code rather than writing it. But
the former should have priority.)
--
Bartc
Ike Naar
May 27, 2012, 9:03:41 AM5/27/12
to
On 2012-05-27, BartC <b...@freeuk.com> wrote:
> Suppose you're delving into a random scene, (or have an extract for use
> elsewhere), and want to be reminded who a character is, you have to start
> ploughing through from page one first until you encounter their first
> mention?
It depends.
> Suppose you're delving into a random scene, (or have an extract for use
> elsewhere), and want to be reminded who a character is, you have to start
> ploughing through from page one first until you encounter their first
> mention?
When a variable is declared on first use, the active scope of the variable
is sometimes reduced to a few lines of code. So, to find the declaration, one
has to plough backward for a few lines. That may take less ploughing than
when the declaration is at the beginning of the function.
BartC
May 27, 2012, 10:46:56 AM5/27/12
to
"Ian Collins" <ian-...@hotmail.com> wrote in message
news:a2e8hg...@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
thing, but without the sort?
--
Bartc
Keith Thompson
May 27, 2012, 10:49:11 AM5/27/12
to
[...]
--
Keith Thompson (The_Other_Keith) ks...@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"
>> 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.
>> 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.
--
Keith Thompson (The_Other_Keith) ks...@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"
pete
May 27, 2012, 1:55:27 PM5/27/12
to
Keith Thompson wrote:
>
> Ian Collins <ian-...@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),
>
> Ian Collins <ian-...@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.
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
Ian Collins
May 27, 2012, 3:17:50 PM5/27/12
to
On 05/27/12 11:25 PM, BartC wrote:
> "Ian Collins"<ian-...@hotmail.com> wrote in message
> news:a2ee73...@mid.individual.net...
>> On 05/27/12 09:36 PM, BartC wrote:
>
>>> Getting back to C, wouldn't macros and enumerations .... also
>>> all benefit from being declared where they are first used?
>
>> I would make them longer, unlike declaring variables when they are needed
>> makes them shorter.
>
> That's another thing; uses of i, j and k for loop indices is fairly
> standard. They probably will be ints, and the formality of having to declare
> them can be kept out of the way instead of making for-loops even longer.
> (Alternatively for-loop variables could be implicitly declared.)
Declaring loop indexes in the loop makes it clear that's what they are
> "Ian Collins"<ian-...@hotmail.com> wrote in message
> news:a2ee73...@mid.individual.net...
>> On 05/27/12 09:36 PM, BartC wrote:
>
>>> Getting back to C, wouldn't macros and enumerations .... also
>>> all benefit from being declared where they are first used?
>
>> I would make them longer, unlike declaring variables when they are needed
>> makes them shorter.
>
> That's another thing; uses of i, j and k for loop indices is fairly
> standard. They probably will be ints, and the formality of having to declare
> them can be kept out of the way instead of making for-loops even longer.
> (Alternatively for-loop variables could be implicitly declared.)
and that they won't spill out.
>> Besides, how do you introduce a const other that where it is initialised?
>
> What do you mean by a const? If it is a name that is to be used in several
> places, then it can also benefit from splitting declaration (and
> initialisation) from it's use.
--
Ian Collins
jacob navia
May 27, 2012, 4:24:09 PM5/27/12
to
Le 27/05/12 19:55, pete a écrit :
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
> I think there's about a zillion combinations of (a) and (b),
> where (a - b) has problems.
Sure.
> where (a - b) has problems.
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
BartC
May 27, 2012, 5:09:56 PM5/27/12
to
"jacob navia" <ja...@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:
>> 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.
(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
pete
May 27, 2012, 5:31:54 PM5/27/12
to
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
>
> ??
>
> 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
"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"
of what "generic qsort function" could possibly mean.
--
pete
Keith Thompson
May 27, 2012, 5:33:15 PM5/27/12
to
"BartC" <b...@freeuk.com> writes:
> "jacob navia" <ja...@spamsink.net> wrote in message
> news:jpu2h5$16r$1...@speranza.aioe.org...
>> Le 27/05/12 19:55, pete a écrit :
> "jacob navia" <ja...@spamsink.net> wrote in message
> news:jpu2h5$16r$1...@speranza.aioe.org...
>>> 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*
>>> 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.)
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.
pete
May 27, 2012, 5:49:07 PM5/27/12
to
#define COMPAR(A, B) (B > A ? -1 : B != A)
--
pete
Philip Lantz
May 28, 2012, 4:38:13 AM5/28/12
to
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
> 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.
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.
io_x
May 28, 2012, 6:39:45 AM5/28/12
to
"jacob navia" <ja...@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));
>
> 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;
>
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
pete
May 28, 2012, 8:18:12 AM5/28/12
to
--
pete
io_x
May 28, 2012, 3:44:30 PM5/28/12
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
news:4fc354b3$0$1390$4faf...@reader2.news.tin.it...
in your pc; here with my little pc, and with my implementation
of list
is too much for me... i get a result only until N=190_000
because if more big, it would
be Malloc_m return 0 in the first loop ...
int testList2(void)
{u32 lista[2]={0}, i, j, r, cr, x;
u8 *pr;
x=Rand_m(); P("x=%u\n", x);
F(i=1, cr=0; i<190000; ++i)
{x=Rand_m();
r=List2PushH(lista, x); cr+=(r==-1);
if(i%100==0 && cr!=0)
{ex: List2Free(lista); R -1;}
}
F(pr=0, x=0; (r=List2Next(lista, &pr))!=1; )
{if(r==-1) G ex;
x+=List2elm(pr);
}
P("\nSomma x=%u\n", x);
if(List2Sortu32(lista)==-1) G ex;
F(pr=0, x=0; (r=List2Next(lista, &pr))!=1; )
{if(r==-1) G ex;
x+=List2elm(pr);
}
P("\nSomma x=%u cr=%u\n", x, cr);
P("\n");List2Free(lista); R 0;
}
Sarah Wren
May 29, 2012, 3:40:00 AM5/29/12
to
news:jprl29$ifd$1...@speranza.aioe.org...
> Hi Ian
>
Are you not ashamed of yourself for asking what you are asking (you've a
history here, not just the one proverbial question)?
At some point, you'll become as wise as me, and I'll become as old as you.
To note, I am older and you are just taking your toys apart and figuring
them out. Hmm?
> Hi Ian
>
Are you not ashamed of yourself for asking what you are asking (you've a
history here, not just the one proverbial question)?
At some point, you'll become as wise as me, and I'll become as old as you.
To note, I am older and you are just taking your toys apart and figuring
them out. Hmm?
jacob navia
May 29, 2012, 3:46:30 AM5/29/12
to
Le 28/05/12 21:44, io_x a écrit :
Thanks
> #define N 10_000_000
> in your pc; here with my little pc, and with my implementation
> of list
> is too much for me... i get a result only until N=190_000
> because if more big, it would
> be Malloc_m return 0 in the first loop ...
Did the library catch correctly the error?
> in your pc; here with my little pc, and with my implementation
> of list
> is too much for me... i get a result only until N=190_000
> because if more big, it would
> be Malloc_m return 0 in the first loop ...
Thanks
io_x
May 29, 2012, 3:59:30 AM5/29/12
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
region returned from the malloc function i use...
i grow the limit until 800000 so here seems ok for
N=700_000 more than 10 time less of 10_000_000...
but i'm happy so, i not like mem limits
if someone reach them there is something wrong
for definition.
> because if more big, it would
> be Malloc_m return 0 in the first loop ...
>
> int testList2(void)
> {u32 lista[2]={0}, i, j, r, cr, x;
> u8 *pr;
>
> x=Rand_m(); P("x=%u\n", x);
> F(i=1, cr=0; i<190000; ++i)
> {x=Rand_m();
> r=List2PushH(lista, x); cr+=(r==-1);
> if(i%100==0 && cr!=0)
> {ex: List2Free(lista); R -1;}
> }
> F(pr=0, x=0; (r=List2Next(lista, &pr))!=1; )
> {if(r==-1) G ex;
> x+=List2elm(pr);
> }
> P("\nSomma x=%u\n", x);
> if(List2Sortu32(lista)==-1) G ex;
> F(pr=0, x=0; (r=List2Next(lista, &pr))!=1; )
> {if(r==-1) G ex;
> x+=List2elm(pr);
> }
> P("\nSomma x=%u cr=%u\n", x, cr);
> P("\n");List2Free(lista); R 0;
> }
io_x
May 29, 2012, 4:06:44 AM5/29/12
to
news:jq1usk$92r$1...@speranza.aioe.org...
it depend of what error you seek...
do you want check if all the list -> pointer to next and prec are
right? do you want to know if someone write all the node
for some error?
than some error can be erased if one write the right
functions and only these write nodes and elements...
but i'm not one expert... i can say what i seen...
Buona Giornata...
do you want check if all the list -> pointer to next and prec are
right? do you want to know if someone write all the node
for some error?
than some error can be erased if one write the right
functions and only these write nodes and elements...
but i'm not one expert... i can say what i seen...
Buona Giornata...
io_x
May 29, 2012, 4:37:58 AM5/29/12
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
news:4fc48250$0$1374$4faf...@reader1.news.tin.it...
>
> "jacob navia" <ja...@spamsink.net> ha scritto nel messaggio
> news:jq1usk$92r$1...@speranza.aioe.org...
>> Le 28/05/12 21:44, io_x a écrit :
>>> #define N 10_000_000
>>> in your pc; here with my little pc, and with my implementation
>>> of list
>>> is too much for me... i get a result only until N=190_000
>>> because if more big, it would
>>> be Malloc_m return 0 in the first loop ...
>>
>> Did the library catch correctly the error?
pheraps you say what if malloc return 0?
> "jacob navia" <ja...@spamsink.net> ha scritto nel messaggio
> news:jq1usk$92r$1...@speranza.aioe.org...
>> Le 28/05/12 21:44, io_x a écrit :
>>> #define N 10_000_000
>>> in your pc; here with my little pc, and with my implementation
>>> of list
>>> is too much for me... i get a result only until N=190_000
>>> because if more big, it would
>>> be Malloc_m return 0 in the first loop ...
>>
>> Did the library catch correctly the error?
than List2Push return -1, List2freeA is call on list,
some memory check on free...
the function return -1, see if some leak, return to OS
no other problem...
io_x
May 29, 2012, 4:58:50 AM5/29/12
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
>> than some error can be erased if one write the right
>> functions and only these write nodes and elements...
"nodes" in my little english dictionary not exist
>> functions and only these write nodes and elements...
pehraps better "knots"
Joachim Schmitz
May 29, 2012, 5:34:50 AM5/29/12
to
io_x wrote:
> "io_x" <a...@b.c.invalid> ha scritto nel messaggio
> news:4fc489a7$0$1386$4faf...@reader1.news.tin.it...
>>> than some error can be erased if one write the right
>>> functions and only these write nodes and elements...
>
> "nodes" in my little english dictionary not exist
> pehraps better "knots"
I guess it is "punto nodale"
> "io_x" <a...@b.c.invalid> ha scritto nel messaggio
> news:4fc489a7$0$1386$4faf...@reader1.news.tin.it...
>>> than some error can be erased if one write the right
>>> functions and only these write nodes and elements...
>
> "nodes" in my little english dictionary not exist
> pehraps better "knots"
Malcolm McLean
May 29, 2012, 6:02:48 AM5/29/12
to
בתאריך יום שלישי, 29 במאי 2012 09:58:50 UTC+1, מאת io_x:
>
> "nodes" in my little english dictionary not exist
> pehraps better "knots"
>
The words have the same root, but now they mean different things.
> "nodes" in my little english dictionary not exist
> pehraps better "knots"
>
io_x
May 29, 2012, 2:09:17 PM5/29/12
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
> int testList2(void)
> {u32 lista[2]={0}, i, j, r, cr, x;
> u8 *pr;
>
> x=Rand_m(); P("x=%u\n", x);
> F(i=1, cr=0; i<190000; ++i)
> {x=Rand_m();
> r=List2PushH(lista, x); cr+=(r==-1);
> if(i%100==0 && cr!=0)
> {ex: List2Free(lista); R -1;}
> }
yes there is at last one error here:
> {u32 lista[2]={0}, i, j, r, cr, x;
> u8 *pr;
>
> x=Rand_m(); P("x=%u\n", x);
> F(i=1, cr=0; i<190000; ++i)
> {x=Rand_m();
> r=List2PushH(lista, x); cr+=(r==-1);
> if(i%100==0 && cr!=0)
> {ex: List2Free(lista); R -1;}
> }
if(cr!=0) G ex;
if(cr!=0) goto ex;
so i were lucky when the program exit with error of function
> F(pr=0, x=0; (r=List2Next(lista, &pr))!=1; )
> {if(r==-1) G ex;
> x+=List2elm(pr);
> }
> P("\nSomma x=%u\n", x);
> if(List2Sortu32(lista)==-1) G ex;
> F(pr=0, x=0; (r=List2Next(lista, &pr))!=1; )
> {if(r==-1) G ex;
> x+=List2elm(pr);
> }
> P("\nSomma x=%u cr=%u\n", x, cr);
pete
Jun 13, 2012, 9:25:47 PM6/13/12
to
Ian Collins wrote:
>
> On 05/27/12 07:30 PM, jacob navia wrote:
> > Le 27/05/12 05:16, Ian Collins a �crit :
> >>
> >> 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:
** 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
>
> 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>
> >>> 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:
> >>>
> >>
> >> 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
/*
> 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)
{
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
pete
Jun 13, 2012, 9:52:57 PM6/13/12
to
pete wrote:
After looking at it more closley,
I think that I may have been wrong,
but please check it anyway.
Thank you.
--
pete
I think that I may have been wrong,
but please check it anyway.
Thank you.
--
pete
jacob navia
Jun 13, 2012, 10:00:44 PM6/13/12
to
Le 14/06/12 03:25, pete a �crit :
> if (pint != NULL&& last_pint> *pint) {
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
> 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
> 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;
> }
>
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
pete
Jun 14, 2012, 12:04:45 AM6/14/12
to
jacob navia wrote:
>
> Le 14/06/12 03:25, pete a écrit :
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
>
> Le 14/06/12 03:25, pete a écrit :
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?
> Thanks for your help.
You're welcome
and I'm sorry about the misunderstanding.
--
pete
0 new messages