Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

God doesn't play dice. -- Albert Einstein


devel / comp.arch.fpga / Re: How long does it take to fill up an array prior to sorting?

SubjectAuthor
* How long does it take to fill up an array prior to sorting?Kevin Simonson
+* Re: How long does it take to fill up an array prior to sorting?David Brown
|`* Re: How long does it take to fill up an array prior to sorting?Kevin Simonson
| `- Re: How long does it take to fill up an array prior to sorting?David Brown
`- Re: How long does it take to fill up an array prior to sorting?gnuarm.del...@gmail.com

1
How long does it take to fill up an array prior to sorting?

<6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=178&group=comp.arch.fpga#178

 copy link   Newsgroups: comp.arch.fpga
X-Received: by 2002:ad4:5444:: with SMTP id h4mr17733460qvt.14.1624243334311; Sun, 20 Jun 2021 19:42:14 -0700 (PDT)
X-Received: by 2002:a37:638b:: with SMTP id x133mr21542270qkb.445.1624243334111; Sun, 20 Jun 2021 19:42:14 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.uzoreto.com!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.fpga
Date: Sun, 20 Jun 2021 19:42:13 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=2601:681:780:4a60:81a:c0a1:fa64:461c; posting-account=qnoIxQoAAABvhb38qjo-00qlUyL4waSR
NNTP-Posting-Host: 2601:681:780:4a60:81a:c0a1:fa64:461c
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>
Subject: How long does it take to fill up an array prior to sorting?
From: 10956...@my.uvu.edu (Kevin Simonson)
Injection-Date: Mon, 21 Jun 2021 02:42:14 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 43
 by: Kevin Simonson - Mon, 21 Jun 2021 02:42 UTC

Most sorting algorithms I've noticed seem to have an interface somewhat like this:

void someAlgorithm ( elemType[] elements);

So to implement this algorithm an application needs to fill the {elements} array, call the {someAlgorithm()} algorithm, and then read out the (sorted) elements of {elements}. For an {elements} object that contains n {elemType}s, how long does it take to fill that array? Is the most efficient way to implement a loop like this:

elemType[] elems = new elemType[ n];
int ix;
for (ix = 0; ix < n; ix++)
{ elems[ ix] = produceElem();
} someAlgorithm( elems);

and then is the most efficient way to read the results of the array something like this:

for (ix = 0; ix < n; ix++)
{ consumeElem( elems[ ix]);
}

This would amount to, for each element, incrementing {ix}, comparing it to {n}, and then actually sending the produced {elemType} to the right position in the array (for filling the array), and then, for each element, incrementing {ix}, comparing it to {n}, and then reading the {elemType} in the corresponding position in the array (for emptying the array). So n+n+n = 3n instructions for each stage, and each instruction requires at least one clock cycle to fetch the instruction, at least one clock cycle to interpret the instruction, and at least one clock cycle to execute the instruction. So that's at least 9n clock cycles to fill the array and at least 9n clock cycles to empty it after calling {someAlgorithm()}.

I've heard that some scientists have found ways to quickly move large blocks of data from one place on disk to another. Does that speed this process up, make it less than the 9n clock cycles I've postulated above?

I've got my eye on sorting of large amounts of data that's actually done in the industry. Do organizations that on a regular basis sort large amounts of data typically take 9n clock cycles to fill up the array, or is there a quicker way to do it that's in general use?

Re: How long does it take to fill up an array prior to sorting?

<sapgbs$m8t$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=179&group=comp.arch.fpga#179

 copy link   Newsgroups: comp.arch.fpga
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.fpga
Subject: Re: How long does it take to fill up an array prior to sorting?
Date: Mon, 21 Jun 2021 09:50:20 +0200
Organization: A noiseless patient Spider
Lines: 62
Message-ID: <sapgbs$m8t$1@dont-email.me>
References: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 21 Jun 2021 07:50:20 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="df33aeeb06c9ad5932ebf6808d84c8f3";
logging-data="22813"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+23X/RSIuixC057TeO8QqQXzfltBO9f8E="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
Thunderbird/68.10.0
Cancel-Lock: sha1:VyeWCVrxYYG10xiNHtl6V0s0b4c=
In-Reply-To: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>
Content-Language: en-GB
 by: David Brown - Mon, 21 Jun 2021 07:50 UTC

On 21/06/2021 04:42, Kevin Simonson wrote:
> Most sorting algorithms I've noticed seem to have an interface somewhat like this:
>
> void someAlgorithm ( elemType[] elements);
>
> So to implement this algorithm an application needs to fill the {elements} array, call the {someAlgorithm()} algorithm, and then read out the (sorted) elements of {elements}. For an {elements} object that contains n {elemType}s, how long does it take to fill that array? Is the most efficient way to implement a loop like this:
>
> elemType[] elems = new elemType[ n];
> int ix;
> for (ix = 0; ix < n; ix++)
> { elems[ ix] = produceElem();
> }
> someAlgorithm( elems);
>
> and then is the most efficient way to read the results of the array something like this:
>
> for (ix = 0; ix < n; ix++)
> { consumeElem( elems[ ix]);
> }
>
> This would amount to, for each element, incrementing {ix}, comparing it to {n}, and then actually sending the produced {elemType} to the right position in the array (for filling the array), and then, for each element, incrementing {ix}, comparing it to {n}, and then reading the {elemType} in the corresponding position in the array (for emptying the array). So n+n+n = 3n instructions for each stage, and each instruction requires at least one clock cycle to fetch the instruction, at least one clock cycle to interpret the instruction, and at least one clock cycle to execute the instruction. So that's at least 9n clock cycles to fill the array and at least 9n clock cycles to empty it after calling {someAlgorithm()}.
>
> I've heard that some scientists have found ways to quickly move large blocks of data from one place on disk to another. Does that speed this process up, make it less than the 9n clock cycles I've postulated above?
>
> I've got my eye on sorting of large amounts of data that's actually done in the industry. Do organizations that on a regular basis sort large amounts of data typically take 9n clock cycles to fill up the array, or is there a quicker way to do it that's in general use?
>

Can I assume, due to your ".edu" address, that you are a student?

You are mixing up a large number of things here, and making a range of
completely unwarranted and wrong assumptions. Your descriptions of the
problems you are considering are so vague as to be pointless - you are
asking how long is a piece of string. And you are posting to a group
that is almost totally and utterly unrelated to the question.

So the obvious response here would be to recommend you go to your
classes and listen, rather than sleep at the back, that you read the
books and do the work - then you'll learn. But it is also possible that
you are working hard and are simply coming up with questions and ideas
that are way ahead of what you have learned. I'd still recommend
learning to walk before worrying about how to run. However, I can give
you a couple of hints.

Timings in processors cannot be counted in cycles like this unless you
are talking about very simple and limited processors, or very
specialised ones. There are endless complications of super-scaler
scheduling, memory delays, and other issues that mean the throughput can
easily be an order of magnitude slower (or sometimes faster) than such a
simple cycle count would suggest.

Timings of loop handling are generally irrelevant (by orders of
magnitude) compared to the time to create, copy or handle the elements.

Filling or handling an array of data scales as O(n) in the size of the
data. Sorting, for the most part, scales as O(n log n). For big
arrays, that means the sorting is the cost, not reading or writing the
array. (In practice, memory speeds, cache usage, disk/IO access, etc.,
are hugely important - but they too affect the sorting part more than
the copying part.)

Re: How long does it take to fill up an array prior to sorting?

<4998d549-a3c5-4dcf-a7f0-f87e171f49d1n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=181&group=comp.arch.fpga#181

 copy link   Newsgroups: comp.arch.fpga
X-Received: by 2002:a37:9b15:: with SMTP id d21mr637817qke.329.1624309641444;
Mon, 21 Jun 2021 14:07:21 -0700 (PDT)
X-Received: by 2002:ad4:5609:: with SMTP id ca9mr21999980qvb.26.1624309641258;
Mon, 21 Jun 2021 14:07:21 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.goja.nl.eu.org!3.eu.feeder.erje.net!feeder.erje.net!fdn.fr!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.fpga
Date: Mon, 21 Jun 2021 14:07:20 -0700 (PDT)
In-Reply-To: <sapgbs$m8t$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2601:681:780:4a60:cd55:3a5b:56bc:4988;
posting-account=qnoIxQoAAABvhb38qjo-00qlUyL4waSR
NNTP-Posting-Host: 2601:681:780:4a60:cd55:3a5b:56bc:4988
References: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com> <sapgbs$m8t$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4998d549-a3c5-4dcf-a7f0-f87e171f49d1n@googlegroups.com>
Subject: Re: How long does it take to fill up an array prior to sorting?
From: 10956...@my.uvu.edu (Kevin Simonson)
Injection-Date: Mon, 21 Jun 2021 21:07:21 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: Kevin Simonson - Mon, 21 Jun 2021 21:07 UTC

David Brown: "Can I assume, due to your '.edu' address, that you are a student?"

Close. I've been admitted into the Senior Citizen Audit Program at Utah Valley University. I turn 62 in September, so I will start classes this Fall. I could just ask my questions in class, but my curiousity is killing me, and it would be nice if I could get it resolved as soon as possible.

My background is actually in Computer Science; I got a BS degree in 1987 and an MS degree in 1994, both at the University of Washington. At this late date my interests are turning to Electrical Engineering; hence my attempt to take classes at UVU.

"And you are posting to a group that is almost totally and utterly unrelated to the question."

Can you tell me which group I should be posting this to?

"Filling or handling an array of data scales as O(n) in the size of the data. Sorting, for the most part, scales as O(n log n)."

That's true for single threaded sorters. It turns out that massively parallel quicksort can get it down to O( (log n)^2). But quicksort still requires the array to be totally filled before the algorithm starts, doesn't it? So it seems the amount of time it takes to enter the elements into the array becomes relevant.

Re: How long does it take to fill up an array prior to sorting?

<sasbos$c8$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=182&group=comp.arch.fpga#182

 copy link   Newsgroups: comp.arch.fpga
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.fpga
Subject: Re: How long does it take to fill up an array prior to sorting?
Date: Tue, 22 Jun 2021 11:50:19 +0200
Organization: A noiseless patient Spider
Lines: 97
Message-ID: <sasbos$c8$1@dont-email.me>
References: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>
<sapgbs$m8t$1@dont-email.me>
<4998d549-a3c5-4dcf-a7f0-f87e171f49d1n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 22 Jun 2021 09:50:20 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="9f0b4532c3bfce2df9509a37c4b42a4f";
logging-data="392"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18cRhdaY15XMNh8bjwDWzXnJUsgmVLXqHA="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
Thunderbird/68.10.0
Cancel-Lock: sha1:tAgrWOilI0lqidlPpAIfz5VVuqc=
In-Reply-To: <4998d549-a3c5-4dcf-a7f0-f87e171f49d1n@googlegroups.com>
Content-Language: en-GB
 by: David Brown - Tue, 22 Jun 2021 09:50 UTC

On 21/06/2021 23:07, Kevin Simonson wrote:
> David Brown: "Can I assume, due to your '.edu' address, that you are
> a student?"
>
> Close. I've been admitted into the Senior Citizen Audit Program at
> Utah Valley University. I turn 62 in September, so I will start
> classes this Fall. I could just ask my questions in class, but my
> curiousity is killing me, and it would be nice if I could get it
> resolved as soon as possible.
>

You are never too old to be a student! What sort of courses are you
doing that raise questions like these?

> My background is actually in Computer Science; I got a BS degree in
> 1987 and an MS degree in 1994, both at the University of Washington.
> At this late date my interests are turning to Electrical Engineering;
> hence my attempt to take classes at UVU.
>

If you have a background in computer science, then surely you know
already that counting cycles like that is completely meaningless in most
situations?

> "And you are posting to a group that is almost totally and utterly
> unrelated to the question."
>
> Can you tell me which group I should be posting this to?

Have you any experience with Usenet? You are using google's interface -
that's okay for searching archives, but an extremely poor interface for
posting or reading regularly. Amongst other things, it fails to follow
or encourage Usenet standards for posting, quoting and attributing. And
these days it suffers more from google's idiotic "throw out the baby
with the bathwater" attitude to censorship - they let people use their
own interface to post spam, conspiracy theories, abuse, etc., and then
they block the entire group because it has been spreading such posts.
(I'm not anti-google at all - merely anti-stupid.)

If you want to use Usenet, get an account at a proper newserver
(news.eternal-september.org is easy and free), and a proper newsreader
(Thunderbird is fine if you don't have any other preferences).

comp.arch.fpga is about programmable logic. Yes, some people here might
make cpu designs, but it is not about software algorithms.

comp.lang.c++ is about C++ (I'm guessing that's what you are using here,
but the snippets are not long enough to be sure). But that's more about
the language than algorithms.

comp.programming is a general programming group. It is dominated by a
couple of unpleasant characters who make huge numbers of nonsense posts
- so you need to filter them out. The others in the group don't start
threads very often, but there are plenty who are ready to contribute to
interesting threads started by others. It is worth a try.

But it might well be that there are other places better suited to
answering your questions these days. I like the Usenet format, and
think it is far more efficient than web-based forums. But the fact is
that there are orders of magnitude more people using things like Stack
Exchange than there are on Usenet.

>
> "Filling or handling an array of data scales as O(n) in the size of
> the data. Sorting, for the most part, scales as O(n log n)."
>
> That's true for single threaded sorters. It turns out that massively
> parallel quicksort can get it down to O( (log n)^2). But quicksort
> still requires the array to be totally filled before the algorithm
> starts, doesn't it? So it seems the amount of time it takes to enter
> the elements into the array becomes relevant.
>

There are a wide variety of sorting algorithms, with different types of
parallelism and different trade-offs, limitations and strengths. And
this is combined with an even wider variety of misconceptions,
misunderstandings, and a failure to distinguish theoretical calculations
from practical reality.

A parallel sorting algorithm run on N processors cannot achieve greater
speedup than a factor of N. Theoretical speeds of O(logĀ² n) and the
like are upper bounds when there is no limit to the number of
processors. /Sometimes/ you have a sorting task where you can use
massive arrays of simple elements with the aim of minimal latency or
maximum throughput when sorting large numbers of small arrays - but that
is going to be very rare.

In reality, sorting comes down to the speed of the data I/O - the
memory, and the caches. Algorithms that are cache-friendly beat those
that are not, even if they look a little slower in the theoretical
calculations. And they are /always/ slower than O(n), even when you
have data suitable for a bucket sort, at least when you have sizes big
enough for the efficiency to be important.

Re: How long does it take to fill up an array prior to sorting?

<ac21b2b5-4ec8-438e-8dc7-0114f2819ca4n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=189&group=comp.arch.fpga#189

 copy link   Newsgroups: comp.arch.fpga
X-Received: by 2002:a0c:fd85:: with SMTP id p5mr20555753qvr.22.1624806452918;
Sun, 27 Jun 2021 08:07:32 -0700 (PDT)
X-Received: by 2002:ac8:47c3:: with SMTP id d3mr3967774qtr.165.1624806452747;
Sun, 27 Jun 2021 08:07:32 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.fpga
Date: Sun, 27 Jun 2021 08:07:32 -0700 (PDT)
In-Reply-To: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=64.237.228.236; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 64.237.228.236
References: <6b12adf9-183f-4131-adf8-bd55877bff5bn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ac21b2b5-4ec8-438e-8dc7-0114f2819ca4n@googlegroups.com>
Subject: Re: How long does it take to fill up an array prior to sorting?
From: gnuarm.d...@gmail.com (gnuarm.del...@gmail.com)
Injection-Date: Sun, 27 Jun 2021 15:07:32 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: gnuarm.del...@gmail. - Sun, 27 Jun 2021 15:07 UTC

On Sunday, June 20, 2021 at 10:42:16 PM UTC-4, Kevin Simonson wrote:
> Most sorting algorithms I've noticed seem to have an interface somewhat like this:
>
> void someAlgorithm ( elemType[] elements);
>
> So to implement this algorithm an application needs to fill the {elements} array, call the {someAlgorithm()} algorithm, and then read out the (sorted) elements of {elements}. For an {elements} object that contains n {elemType}s, how long does it take to fill that array? Is the most efficient way to implement a loop like this:
>
> elemType[] elems = new elemType[ n];
> int ix;
> for (ix = 0; ix < n; ix++)
> { elems[ ix] = produceElem();
> }
> someAlgorithm( elems);
>
> and then is the most efficient way to read the results of the array something like this:
>
> for (ix = 0; ix < n; ix++)
> { consumeElem( elems[ ix]);
> }
>
> This would amount to, for each element, incrementing {ix}, comparing it to {n}, and then actually sending the produced {elemType} to the right position in the array (for filling the array), and then, for each element, incrementing {ix}, comparing it to {n}, and then reading the {elemType} in the corresponding position in the array (for emptying the array). So n+n+n = 3n instructions for each stage, and each instruction requires at least one clock cycle to fetch the instruction, at least one clock cycle to interpret the instruction, and at least one clock cycle to execute the instruction. So that's at least 9n clock cycles to fill the array and at least 9n clock cycles to empty it after calling {someAlgorithm()}.

A couple of things, your breakdown of the code timing is not accurate for any particular CPU or computer. These things vary a great deal with many types of optimization in software and hardware.

But more importantly, why do you care about this particular part of the process? Sorting algorithms are typically dependent on data size by some large factor such as O(x^2) although it's been a long time since I've looked and some might be better at O(x log(x)) or similar. Still, for any large data set that is going to dominate the operation time. Then there is the issue of the data being stored on mass storage for loading the memory array which will again swamp the sorting time unless the data size is very large.

This reminds me that many of these sorting algorithms were written before hard drives were invented and they were working from magnetic tape!

> I've heard that some scientists have found ways to quickly move large blocks of data from one place on disk to another. Does that speed this process up, make it less than the 9n clock cycles I've postulated above?

Disk and "quick" do not go together. The way to quickly move data on disk is to not move it but change the pointer to it.

> I've got my eye on sorting of large amounts of data that's actually done in the industry. Do organizations that on a regular basis sort large amounts of data typically take 9n clock cycles to fill up the array, or is there a quicker way to do it that's in general use?

For large amounts of data no one cares about 9n clock cycles since it will take many, many more to do the sort. At least that's what I recall. Like I said, it's been a long time.

BTW, this post was made via Google Groups even if it did make my fingers bleed.

--

Rick C.

- Get 1,000 miles of free Supercharging
- Tesla referral code - https://ts.la/richard11209

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor