If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below. |
|
|
Thread Tools | Rate Thread | Display Modes |
#46
|
|||
|
|||
C is not a low level language
Wouter Verhelst writes:
On 25/02/2019 20:40, nospam wrote: In article , Wouter Verhelst wrote: code that is not called can't slow anything down. That's actually not true. it is true. what matters is the code that *is* called. You're saying that the code can't slow thing down if it's not called. That's a fairly absolute statement; I just showed you a counter-example, and so did Scott. So your absolute statement is just *wrong*. Code that is not called but is compiled in will use up space in a memory page. If that means the code segment of the program grows beyond a page boundary, that may then mean an extra page fault will need to be handled when part of the program is swapped out, which would otherwise not be necessary. that's more theoretical than anything real. It does happen though, and the more "not called" code you add to a program the larger the chances of this happening. Actually it happens more often than you think, which is one reason that execution-driven feedback into code layout is so effective in increasing application performance for certain classes of applications. nearly everything is i/o bound, and then there are all the other processes... Not at all true, particularly with respect to the applications where performance matters (HPC, in-memory databases, etc). Windows desktop applications aren't the whole world, you know. |
Ads |
#47
|
|||
|
|||
C is not a low level language
On Tue, 26 Feb 2019 10:58:09 +0100, "Pascal J. Bourguignon"
wrote: Robert Wessel writes: bubble sort is very easy to write, it's just not fast. Insertion sort is even easier to write. And it's usually twice as fast as bubble sort. Bubble sort is the fastest, on a vector already sorted. It's O(n) with the best constants in this best case. I've heard that assertion multiple time, but have not seen much evidence to back it up. In some tests I've run over the years, bubble sort and insertion sort on already sorted datasets tend to have performance very nearly the same, if not identical, subject to implementation vagaries. If there is an advantage, it's very small. Consider (MSVC, /Ox): #include windows.h #define ITER 1000000 #define SZ 10000 int a[SZ]; void bubblesort(int *a, int n) { int i, j; for (j = 0; jn; j++) { int swapped = 0; i = 0; while (in-1) { if (a[i] a[i+1]) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; swapped = 1; } i++; } if (!swapped) break; n--; } } void insertionsort(int *a, int n) { int i, j; for (j = 1; jn; j++) { i = j; while (i0 && a[i] a[i-1]) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; i--; } } } int main() { int i; DWORD starttick, elapsedtick; for (i=0; iSZ; i++) a[i] = i; printf("Array size: %i, iterations: %i\n", SZ, ITER); starttick = GetTickCount(); for (i=0; iITER; i++) bubblesort(a, SZ); elapsedtick = GetTickCount() - starttick; printf("Bubble sort: %.10fms/iter\n", (double)elapsedtick/ITER); starttick = GetTickCount(); for (i=0; iITER; i++) bubblesort(a, SZ); elapsedtick = GetTickCount() - starttick; printf("Insertion sort: %.10fms/iter\n", (double)elapsedtick/ITER); return 0; } *** G:\wesseltest227 Array size: 10000, iterations: 1000000 Bubble sort: 0.0183590000ms/iter Insertion sort: 0.0185160000ms/iter G:\wesseltest227 Array size: 10000, iterations: 1000000 Bubble sort: 0.0182500000ms/iter Insertion sort: 0.0180470000ms/iter G:\wesseltest227 Array size: 10000, iterations: 1000000 Bubble sort: 0.0182650000ms/iter Insertion sort: 0.0182500000ms/iter |
#48
|
|||
|
|||
C is not a low level language
Robert Wessel writes:
On Tue, 26 Feb 2019 10:58:09 +0100, "Pascal J. Bourguignon" wrote: Robert Wessel writes: bubble sort is very easy to write, it's just not fast. Insertion sort is even easier to write. And it's usually twice as fast as bubble sort. Bubble sort is the fastest, on a vector already sorted. It's O(n) with the best constants in this best case. I've heard that assertion multiple time, but have not seen much evidence to back it up. In some tests I've run over the years, bubble sort and insertion sort on already sorted datasets tend to have performance very nearly the same, if not identical, subject to implementation vagaries. If there is an advantage, it's very small. Consider (MSVC, /Ox): #include windows.h #define ITER 1000000 #define SZ 10000 int a[SZ]; Ok, now try it with a dataset that doesn't fit into the typical L1D cache. (e.g. #define SZ 10000000 // ~400MB). |
#49
|
|||
|
|||
C is not a low level language
On 26/02/2019 18:11, Scott Lurndal wrote:
Robert Wessel writes: On Tue, 26 Feb 2019 10:58:09 +0100, "Pascal J. Bourguignon" wrote: Robert Wessel writes: bubble sort is very easy to write, it's just not fast. Insertion sort is even easier to write. And it's usually twice as fast as bubble sort. Bubble sort is the fastest, on a vector already sorted. It's O(n) with the best constants in this best case. I've heard that assertion multiple time, but have not seen much evidence to back it up. In some tests I've run over the years, bubble sort and insertion sort on already sorted datasets tend to have performance very nearly the same, if not identical, subject to implementation vagaries. If there is an advantage, it's very small. Consider (MSVC, /Ox): #include windows.h #define ITER 1000000 #define SZ 10000 int a[SZ]; Ok, now try it with a dataset that doesn't fit into the typical L1D cache. (e.g. #define SZ 10000000 // ~400MB). You have a typo so it's not clear if you mean 10M items or 100M. But with either, timings are pretty much identical, unoptimised. Optimised, bubble sort is still ahead. However, nobody would ever use bubble sort with N=1000, let along 10M or 100M. |
#50
|
|||
|
|||
C is not a low level language
Robert Wessel writes:
On Tue, 26 Feb 2019 10:58:09 +0100, "Pascal J. Bourguignon" wrote: Robert Wessel writes: bubble sort is very easy to write, it's just not fast. Insertion sort is even easier to write. And it's usually twice as fast as bubble sort. Bubble sort is the fastest, on a vector already sorted. It's O(n) with the best constants in this best case. I've heard that assertion multiple time, but have not seen much evidence to back it up. In some tests I've run over the years, bubble sort and insertion sort on already sorted datasets tend to have performance very nearly the same, if not identical, subject to implementation vagaries. If there is an advantage, it's very small. bubblesort still uses less comparisons: ------------------------------------------------------------ #include stdio.h int a[]={1,2,3,4,5,6,7,8,9, 10,11,12,13,14,15,16,17,18,19}; int bubblesort(int *a, int n) { int count=0; int i, j; for (j = 0; count++,jn; j++) { int swapped = 0; i = 0; while (count++,in-1) { if (count++,a[i] a[i+1]) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; swapped = 1; } i++; } if (!swapped) break; n--; } return count; } int insertionsort(int *a, int n) { int count=0; int i, j; for (j = 1; count++,jn; j++) { i = j; while ((count++,i0) && (count++,a[i] a[i-1])) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; i--; } } return count; } int main() { printf("bubblesort = %5d comparisons\n",bubblesort(a, sizeof(a)/sizeof(a[0]))); printf("insertionsort = %5d comparisons\n",insertionsort(a, sizeof(a)/sizeof(a[0]))); return 0; } ------------------------------------------------------------ -*- mode: compilation; default-directory: "~/" -*- Compilation started at Tue Feb 26 19:22:01 SRC="/Users/pjb/s.c" ; EXE="s" ; gcc -I. -L. -g3 -ggdb3 -o ${EXE} ${SRC} && ./${EXE} && echo status = $? bubblesort = 38 comparisons insertionsort = 55 comparisons status = 0 Compilation finished at Tue Feb 26 19:22:05 -- __Pascal J. Bourguignon__ http://www.informatimago.com |
#51
|
|||
|
|||
C is not a low level language
"Pascal J. Bourguignon" writes:
Robert Wessel writes: On Tue, 26 Feb 2019 10:58:09 +0100, "Pascal J. Bourguignon" wrote: Robert Wessel writes: bubble sort is very easy to write, it's just not fast. Insertion sort is even easier to write. And it's usually twice as fast as bubble sort. Bubble sort is the fastest, on a vector already sorted. It's O(n) with the best constants in this best case. I've heard that assertion multiple time, but have not seen much evidence to back it up. In some tests I've run over the years, bubble sort and insertion sort on already sorted datasets tend to have performance very nearly the same, if not identical, subject to implementation vagaries. If there is an advantage, it's very small. Actually, the fun is with quicksort: #include stdio.h int a[]={1,2,3,4,5,6,7,8,9, 10,11,12,13,14,15,16,17,18,19}; #define swap(a,b) do{int t=a;a=b;b=t;}while(0) int quicksort_count=0; int quicksort_calls=0; int partition(int*a,int lo, int hi){ int pivot=a[hi]; int i=lo; int j; for(j=lo;quicksort_count++,jhi-1;j++){ if(quicksort_count++,a[j]pivot){ swap(a[i],a[j]); i++;}} swap(a[i],a[hi]); return i;} void quicksort(int*a,int lo, int hi){ if(quicksort_count++,lohi){ int p=(quicksort_calls++,partition(a,lo,hi)); quicksort_calls++,quicksort(a,lo,p-1); quicksort_calls++,quicksort(a,p+1,hi);}} void qsort(int *a, int n){ quicksort_count=0; quicksort_calls=1,quicksort(a,0,n-1);} int bubblesort(int *a, int n) { int count=0; int i, j; for (j = 0; count++,jn; j++) { int swapped = 0; i = 0; while (count++,in-1) { if (count++,a[i] a[i+1]) { swap(a[i],a[i+1]); swapped = 1; } i++; } if (!swapped) break; n--; } return count; } int insertionsort(int *a, int n) { int count=0; int i, j; for (j = 1; count++,jn; j++) { i = j; while ((count++,i0) && (count++,a[i] a[i-1])) { swap(a[i],a[i+1]); i--; } } return count; } int main() { printf("bubblesort = %5d comparisons\n",bubblesort(a, sizeof(a)/sizeof(a[0]))); printf("insertionsort = %5d comparisons\n",insertionsort(a, sizeof(a)/sizeof(a[0]))); qsort(a, sizeof(a)/sizeof(a[0])); printf("quicksort = %5d comparisons and very much worse, %5d calls\n",quicksort_count,quicksort_calls); return 0; } /* -*- mode: compilation; default-directory: "~/" -*- Compilation started at Tue Feb 26 19:37:07 SRC="/Users/pjb/s.c" ; EXE="s" ; gcc -I. -L. -g3 -ggdb3 -o ${EXE} ${SRC} && ./${EXE} && echo status = $? bubblesort = 38 comparisons insertionsort = 55 comparisons quicksort = 190 comparisons and very much worse, 28 calls status = 0 Compilation finished at Tue Feb 26 19:37:07 */ Function calls can easily be a hundred of times slower than a mere comparison. But even counting for the best, the function calls above will have to write 5 words (the parameters, the link and the return address at least), and read two words (the link and the return address), plus the actual JSR, compared to two reads for a single comparison, so at best it's 5 times slower than a comparison. That gives at least 330 equivalent-comparison for quicksort, a 10x overhead in comparisons. I would say that the break even would cover quite a few swaps… For arrays almost sorted, I'd really avoid quicksort. -- __Pascal J. Bourguignon__ http://www.informatimago.com |
#52
|
|||
|
|||
C is not a low level language
nospam
Mon, 25 Feb 2019 17:17:49 GMT in alt.windows7.general, wrote: I think it is good for programmers to have some experience of assembly, and to have understanding of it - it helps give a better appreciation of how things work underneath, and can lead to the programmer writing better high-level code (especially on smaller systems). But that is different from actually writing assembly for real work. what matters the most are good algorithms, and knowing assembly does not help with that. IMO, I believe it does. -- Friends help you move. Real friends help you move bodies. |
#53
|
|||
|
|||
C is not a low level language
Wouter Verhelst
Mon, 25 Feb 2019 18:25:35 GMT in alt.windows7.general, wrote: On 25/02/2019 19:17, nospam wrote: what matters the most are good algorithms, and knowing assembly does not help with that. What helps with that is understanding of how a computer works; understanding the difference between registers and memory locations, and understanding how a processor performs calculations and stores the results of those calculations. It's impossible to write assembly language without at least a basic understanding of how computers work, and it's definitely the case that writing assembly language helps you learn that a bit more; so in that respect it most certainly does help with writing good algorithms. Agreed! -- Friends help you move. Real friends help you move bodies. |
#54
|
|||
|
|||
C is not a low level language
|
#55
|
|||
|
|||
C is not a low level language
In article , Diesel
wrote: Windows desktop applications aren't the whole world, you know. nospam doesn't, afaik, write windows desktop applications. not currently, but i have in the past. They write apps for Apple based products. cell phones primarily I believe, in a scripting language. not even close to correct, and not even possible, given that both android and ios apps are not written in a scripting language. So...I dunno what level of programmer or coder you'd actually consider the individual to be. a rather successful one. |
Thread Tools | |
Display Modes | Rate This Thread |
|
|