A Windows XP help forum. PCbanter

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.

Go Back   Home » PCbanter forum » Microsoft Windows 7 » Windows 7 Forum
Site Map Home Register Authors List Search Today's Posts Mark Forums Read Web Partners

C is not a low level language



 
 
Thread Tools Rate Thread Display Modes
  #46  
Old February 26th 19, 05:29 PM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Scott Lurndal
external usenet poster
 
Posts: 5
Default 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  
Old February 26th 19, 05:53 PM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Robert Wessel
external usenet poster
 
Posts: 2
Default 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  
Old February 26th 19, 07:11 PM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Scott Lurndal
external usenet poster
 
Posts: 5
Default 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  
Old February 26th 19, 07:24 PM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Bart[_7_]
external usenet poster
 
Posts: 4
Default 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  
Old February 26th 19, 07:24 PM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Pascal J. Bourguignon
external usenet poster
 
Posts: 3
Default 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  
Old February 26th 19, 07:44 PM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Pascal J. Bourguignon
external usenet poster
 
Posts: 3
Default 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  
Old March 5th 19, 05:29 AM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Diesel
external usenet poster
 
Posts: 344
Default 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  
Old March 5th 19, 05:29 AM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
Diesel
external usenet poster
 
Posts: 344
Default 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.
  #55  
Old March 5th 19, 05:43 AM posted to alt.windows7.general,comp.lang.c,comp.programming,alt.comp.os.windows-10
nospam
external usenet poster
 
Posts: 4,718
Default 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
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off






All times are GMT +1. The time now is 11:14 AM.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright ©2004-2024 PCbanter.
The comments are property of their posters.