Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Sun, 27 May 2012 06:15:03 -0500 Message-ID: <4FC20CB5.2AD3@mindspring.com> Date: Sun, 27 May 2012 07:15:01 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: Open letter to Ian Collins References: Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Lines: 251 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.217.211 X-Trace: sv3-IHZCECSL2H6PI8D8cOfUDsT7797nEhA1eKfpCEGQE4blzO23uuEEhrC3UiGnU8Nk6xKWl1P0J1KxI6t!RfL/TaBHpejd/mvwa3OMt/5YUPIFZ4rX6QaBc03hJfCu7jR1PNOMUWC+Te4dChE2ujRaw0+dANPT!y0JXg6S8lUI= X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 8493 Xref: csiph.com comp.lang.c: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 #include #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 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 #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