This is so hard to measure! What's a reasonable reference system?
The last time I measured, radixsort and mergesort had sizes where they were
better. Now, on my Alder Lake CPU, quicksort beats the lot, at all sizes,
integer and float. I don't see why it changed so much.
There is still a sizable niche for small-range integer sort at all lengths,
but the range decreases with length.
Henry Rich
On 2/3/2023 9:59 PM, Marshall Lochbaum wrote:
> In case it helps, I took the following measurement with bencharray.
> Looks like the parts other than those plateaus in the middle have gotten
> faster since 9.03, although they were still steps up before. The input
> ranges from -2^31 to 1-~2^31.
>
> https://raw.githubusercontent.com/gist/mlochbaum/40952f8d28ef745dc2d83d8278908ca8/raw/sort-rand-i32-x-j.svg
>
> In the key, ∧ is /:~ and ⍋ is /: . Same for ∨ ⍒ in the other direction.
>
> Reproduce with https://github.com/mlochbaum/bencharray and the following
> command; requires Unix and a BQN install and takes a minute or two to
> run. Output in output/plot/sort-rand-i32-x-j.svg .
>
> $ ./benchmark.bqn all j sort-rand-i32
>
> Marshall
>
> On Fri, Feb 03, 2023 at 06:08:32PM -0500, Henry Rich wrote:
> > Integer sort chooses between 4 algorithms based on timings we make every now
> > and then. It's been a few years since we tuned it.
> >
> > 100000 integers or more uses mergesort; 50000-99999 uses radixsort.
> >
> > It looks like I'd better retune that. Thanks for the tip.
> >
> > Henry Rich
> >
> > On 2/3/2023 5:01 PM, vadim wrote:
> > > So I tried to begin to implement "split into small sub-tasks", but got
> > > stuck before any meaningful step, at what may be another version 9 issue
(?)
> > >
> > > Though I remember " DO NOT give an x argument to 6!:2", in tests below
> > > there is x argument to catch solid time. Otherwise, I could cut 10^7
> > > numbers into ~100 ranges to sort each (closer to my real task), then there
> > > will be no x argument, with approx. the same "solid" time difference
caught
> > > (decimal point moved to the right 2 places of course), but cutting would
> > > mask the real issue.
> > >
> > > 100 (6!:2) '/:~ nn' [ nn =: ? N $ 10^9 [ N =: 100000
> > >
> > > 0.00263482
> > > 100 (6!:2) '/:~ nn' [ nn =: ? N $ 10^9 [ N =: 99999
> > >
> > > 0.0073261
> > > 100 (6!:2) '}./:~ nn,_1' [ nn =: ? N $ 10^9 [ N =: 99999
> > >
> > > 0.00298486
> > >
> > > If I reboot into Linux, it's not 3x, but 4x difference between tests 1 and
> > > 2. Test 3 is like ridiculous advice "don't sort 99999 (nor 99000, perhaps)
> > > numbers; instead pad with throw-away values to 10^5 numbers. I hope my
> > > result is not CPU-model specific, and you can observe something similar.
> > >
> > > No issue in 8.07.
> > >
> > > Best regards,
> > > Vadim
> > >
> > >
> > > On Fri, Jan 27, 2023 at 6:18 PM Henry Rich <henryhr...@gmail.com> wrote:
> > >
> > > > J9.04 is frozen for the release, but J9.05 will follow. This thread has
> > > > convinced me that sorting large arrays can be greatly improved by
> > > > multithreading, and also that I can reduce the threading overhead.
> > > >
> > > > Henry Rich
> > > >
> > > > On 1/27/2023 6:07 AM, vadim wrote:
> > > > > > What result do you get when you use this syntax?
> > > > > "Don't use master thread, use worker threads only", correct? So, I'm
> > > > > allocating 3 workers for 4 equal pieces of work; 3 workers finish
doing
> > > > > their task each, then 2 of them are idle, and 1 alone does the 4th
part?
> > > > >
> > > > > Interestingly, with literals I get predictable time increase from ~400 ms
> > > > > to ~650 ms. Which concurs, more or less. With integers, I get the same
> > > > ~440
> > > > > ms. How very strange. And it's the same ~420 ... 440 ms if I cut ints
> > > > into
> > > > > 2 or 3 parts (master thread is idle then).
> > > > >
> > > > > -------------
> > > > > I don't know if "parallelizable primitives" (including "sort") will
> > > > arrive
> > > > > with 9.04 release, and maybe what follows was already mentioned in
> > > > > community, but with sorting literals there's effective and very lazy
way
> > > > to
> > > > > gain speed through using threads as they are implemented now:
> > > > >
> > > > > (6!:2) '/:~ lits'
> > > > >
> > > > > 1.37036
> > > > >
> > > > > (6!:2) '/:~ ;cut_by /:~t.(0$0);.0 lits'
> > > > >
> > > > > 0.665364
> > > > >
> > > > > 1 T. ''
> > > > >
> > > > > 3
> > > > > -------------
> > > > > Henry, I only have shallow understanding, my practical point of view
was
> > > > > "try to divide work into preferably large and easy to manage parts,
then
> > > > > oversee the whole gang of workers are busy and none of them slacks".
> > > > Thank
> > > > > you very much for the detailed explanation, this cutting into very
small
> > > > > pieces is new to me, I'll now see if I can implement it in practice.
> > > > > Sorting is only part of a larger whole; it's just that I noticed
> > > > > interesting results while experimenting.
> > > > >
> > > > >
> > > > > Best regards,
> > > > > Vadim
> > > > >
> > > > >
> > > > > On Fri, Jan 27, 2023 at 12:11 AM Ak O <akin...@gmail.com> wrote:
> > > > >
> > > > > > Hi Vadim,
> > > > > >
> > > > > > What result do you get when you use this syntax?
> > > > > >
> > > > > > ; cut_by /:~t.(<'worker';1);.0 ints
> > > > > >
> > > > > > Ak.
> > > > > >
> > > > > >
> > > > > > On Thu., Jan. 26, 2023, 08:46 Henry Rich, <henryhr...@gmail.com> wrote:
> > > > > >
> > > > > > > 1. Make sure you turn off all browsers etc. when you time
> > > > multrithreaded
> > > > > > > code.
> > > > > > >
> > > > > > > 2. DO NOT give an x argument to 6!:2. Repeated execution of the same
> > > > > > > sentence may tend to migrate values into the core they will be
used in,
> > > > > > > which will underestimate the time required for a single run. If
you
> > > > > > > have to time anything complicated you may have to put in your own
> > > > timing
> > > > > > > points.
> > > > > > >
> > > > > > > 3. 'Thread overhead' is more than just data movement. It includes time
> > > > > > > required to lock variable-name lookups and contention for D3$.
The
> > > > sort
> > > > > > > of 8-byte literals uses a merge sort IIRC, while the sort of
integers
> > > > > > > uses a lovingly-coded quicksort. The quicksort is faster, as you
can
> > > > > > > see. Mergesort is very cache-friendly: it reads and writes to
memory
> > > > > > > sequentially. Quicksort hops around, storing single words into two
> > > > > > > different streams. On a single thread that doesn't matter much,
but
> > > > > > > with multiple threads and arguments far larger than D3$, the
writing
> > > > > > > spills to DRAM: mergesort needs only one open DRAM page per thread
> > > > while
> > > > > > > quicksort needs two per thread. That will have to make a
difference;
> > > > > > > how much I don't know.
> > > > > > >
> > > > > > > 4. If you want to split sorting into tasks, split it so that each task
> > > > > > > fits into D2$ of a core. With 10M numbers (80MB) and a machine
with
> > > > 1MB
> > > > > > > D2$, let each task have 125K numbers. Experiment with smaller
blocks.
> > > > > > > When you have the right size, the thread overhead will be
comparable to
> > > > > > > the time spent making two copies of the whole array.
> > > > > > >
> > > > > > > 5. If you find that you can reduce the overhead that far, we could have
> > > > > > > a faster way to sort in J using multithreads: split the array
into as
> > > > > > > many pieces as needed and sort them efficiently in threads, then
> > > > > > > transfer the data back to the master thread which merges the
ordered
> > > > > > > strings. The transfer back to the master thread is unavoidable,
but
> > > > the
> > > > > > > time required to merge (a reheaping operation) would be completely
> > > > > > > hidden under the transfer time.
> > > > > > >
> > > > > > > 6. Currently, starting a thread realizes any virtual argument in the
> > > > > > > master thread. It would be better to realize it in the worker
thread
> > > > > > > where the data is needed.
> > > > > > >
> > > > > > > Henry Rich
> > > > > > >
> > > > > > > On 1/25/2023 6:11 PM, vadim wrote:
> > > > > > > > Thank you for fixing the issue and for explanation. I would
appreciate
> > > > > > it
> > > > > > > > if you could look into the performance issue I'm observing with
my
> > > > > > > > multi-threaded example (reduced to uselessness for sake of
> > > > > > presentation,
> > > > > > > > though). I will of course accept "that's how things are with
> > > > > > CPUs/memory"
> > > > > > > > and adjust expectations accordingly, and I understand results
depend
> > > > on
> > > > > > > > hardware and dataset very much. Too small a chance it's J issue.
> > > > > > > >
> > > > > > > > The question concerns sorting data (I'm not doing the '+/' in threads
> > > > > > > :)).
> > > > > > > > I have 4 cores CPU, so I start 3 additional threads:
> > > > > > > >
> > > > > > > > {{ for. i. 3 do. 0 T. 0 end. }} ''
> > > > > > > >
> > > > > > > > Suppose I have literal data, 10 million rows 8 bytes each:
> > > > > > > >
> > > > > > > > lits =: a. {~ ? ((1 * 10^7), 8) $ 256
> > > > > > > > q =: >. -: -: # lits
> > > > > > > > cut_by =: q ,:~ "0 q * i. 4
> > > > > > > > quarter =: q {. lits
> > > > > > > >
> > > > > > > > 4 (6!:2) '/:~ lits'
> > > > > > > > 1.37698
> > > > > > > > 4 (6!:2) '/:~ quarter'
> > > > > > > > 0.308181
> > > > > > > > 4 (6!:2) '; cut_by /:~t.(0$0);.0 lits'
> > > > > > > > 0.414603
> > > > > > > >
> > > > > > > > Excellent, times I see match nicely, I understand there's overhead
> > > > with
> > > > > > > > threads. Next, there are 10 millions of 8-byte integers:
> > > > > > > >
> > > > > > > > ints =: ? (1 * 10^7) $ (10^18)
> > > > > > > > q =: >. -: -: # ints
> > > > > > > > cut_by =: q ,:~ "0 q * i. 4
> > > > > > > > quarter =: q {. ints
> > > > > > > >
> > > > > > > > 4 (6!:2) '/:~ ints'
> > > > > > > > 0.561057
> > > > > > > > 4 (6!:2) '/:~ quarter'
> > > > > > > > 0.124735
> > > > > > > > 4 (6!:2) '; cut_by /:~t.(0$0);.0 ints'
> > > > > > > > 0.441807
> > > > > > > >
> > > > > > > > And I don't like this third time. There's roughly the same amount of
> > > > > > data
> > > > > > > > for "threads overhead". My expectation for this result was
approx.
> > > > > > > 150-200
> > > > > > > > ms or so.
> > > > > > > >
> > > > > > > > In fact, looking at 415 ms for literals and 442 ms for numbers irked
> > > > me
> > > > > > > > into temptation:
> > > > > > > >
> > > > > > > > head =. (3&(3!:4) 16be2), ,|."1 (3&(3!:4)"0) 4,q,1,q
> > > > > > > >
> > > > > > > > _8 ]\ a. i. head
> > > > > > > >
> > > > > > > > 226 0 0 0 0 0 0 0
> > > > > > > >
> > > > > > > > 0 0 0 0 0 0 0 4
> > > > > > > >
> > > > > > > > 0 0 0 0 0 38 37 160
> > > > > > > >
> > > > > > > > 0 0 0 0 0 0 0 1
> > > > > > > >
> > > > > > > > 0 0 0 0 0 38 37 160
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > > to_bytes =: 5&}. @: (_8&(]\)) @: (2&(3!:1))
> > > > > > > >
> > > > > > > > from_bytes =: (3!:2) @: (head&,) @: ,
> > > > > > > >
> > > > > > > >
> > > > > > > > (from_bytes /:~ to_bytes quarter) -: (/:~ quarter) NB. sane still?
> > > > > > > >
> > > > > > > > 1
> > > > > > > >
> > > > > > > >
> > > > > > > > 4 (6!:2) ';cut_by (from_bytes @: /:~ @: to_bytes)t.(0$0);.0 ints'
> > > > > > > >
> > > > > > > > 0.51177
> > > > > > > >
> > > > > > > >
> > > > > > > > Ah, it didn't work. But perhaps it could with certain data, CPU model,
> > > > > > > > number of cores? So my question is if you could confirm that it
> > > > (slower
> > > > > > > > than I expected speed with numerical sort in threads) is
neither J
> > > > > > issue,
> > > > > > > > nor 't.', nor '/:~'. Sorry if I wasted your time.
> > > > > > > >
> > > > > > > > Best regards,
> > > > > > > > Vadim
> > > > > > > >
> > > > > > > >
> > > > > > > > On Wed, Jan 25, 2023 at 8:02 PM Henry Rich <henryhr...@gmail.com>
> > > > > > wrote:
> > > > > > > > > Fixed for the release. Thanks for the clear report. The
problem was
> > > > > > > > > specific to the forms you mentioned. Workaround: use
> > > > > > > > >
> > > > > > > > > < @: ((+/) @:]) instead of < @: (+/) @:]
> > > > > > > > >
> > > > > > > > > The form <@:f is given special treatment. Your form was incorrectly
> > > > > > > > > being given that treatment.
> > > > > > > > >
> > > > > > > > >
> > > > > > > > > If t. in cut is not meeting your expectations, perhaps you should
> > > > > > adjust
> > > > > > > > > your expectations. Verbs like (+/) will not benefit from
threading
> > > > in
> > > > > > > > > most cases, and may slow down considerably. +/;.0 might be
even
> > > > > > worse.
> > > > > > > > > Why? Because +/ is totally limited by the speed of reading
from
> > > > > > > > > memory. If the data fits in level-2 data cache (D2$) many
cores are
> > > > > > no
> > > > > > > > > faster than one.
> > > > > > > > >
> > > > > > > > > In fact they are much slower, because only one core has the data in
> > > > > > > > > D2$. The rest have to transfer the data from the bottom of
the ocean
> > > > > > > > > (i. e. from the core with the data through D3$) or from the
moon
> > > > > > > > > (SDRAM). They are spending their time waiting for responses
from
> > > > > > > memory.
> > > > > > > > > +/;.0 creates a virtual block for each section and passes
that to +/
> > > > .
> > > > > > > > > There is no need to move the data except for the reading
required by
> > > > > > +/
> > > > > > > > > . If you run the +/ in a thread, the virtual block must be
realized
> > > > > > > > > with an explicit copy from the bottom of the ocean. That
doesn't add
> > > > > > > > > much, because once the copy is made the data will be in D2$
of the
> > > > > > > > > receiving core, but it is a small slowdown.
> > > > > > > > >
> > > > > > > > > A thread needs to be able to run in its own core until it has done
> > > > > > > > > reads+writes to D1$/D2$ at least, say, 100 times the size of
its
> > > > > > > > > arguments+result. +/ . * is a perfect example. On large
matrices
> > > > the
> > > > > > > > > arguments are cycled through repeatedly.
> > > > > > > > >
> > > > > > > > > Henry Rich
> > > > > > > > >
> > > > > > > > > On 1/25/2023 7:08 AM, vadim wrote:
> > > > > > > > > > Hi, please consider this:
> > > > > > > > > >
> > > > > > > > > > ((0,:2),:(2,:2)) (< @: +: @: ]);.0 i. 4
> > > > > > > > > > +---+---+
> > > > > > > > > > |0 1|2 3|
> > > > > > > > > > +---+---+
> > > > > > > > > > ((0,:2),:(2,:2)) (< @: (+/) @: ]);.0 i. 4
> > > > > > > > > > +---+---+
> > > > > > > > > > |0 1|2 3|
> > > > > > > > > > +---+---+
> > > > > > > > > > ((0,:2),:(2,:2)) (< @: (\:~) @: ]);.0 i. 4
> > > > > > > > > > +---+---+
> > > > > > > > > > |0 1|2 3|
> > > > > > > > > > +---+---+
> > > > > > > > > >
> > > > > > > > > >
> > > > > > > > > > No issues in 8.07; and a bug (that's what I'd call it) in 9.03 and
> > > > > > > 9.04.
> > > > > > > > > > Looks like it happens if the left arg has multiple ranges;
and a
> > > > verb
> > > > > > > to
> > > > > > > > > > apply is composed with "same" and "box" verbs as first and
last in
> > > > > > > > > > sequence. But it's at 1st glance only. Sometimes omitting
> > > > parentheses
> > > > > > > > would
> > > > > > > > > > help (which clearly means parsing issue?). All these produce
> > > > expected
> > > > > > > > > > output:
> > > > > > > > > >
> > > > > > > > > > (2,:2) (< @: +: @: ]);.0 i. 4
> > > > > > > > > > +---+
> > > > > > > > > > |4 6|
> > > > > > > > > > +---+
> > > > > > > > > > ((0,:2),:(2,:2)) (] @: +: @: ]);.0 i. 4
> > > > > > > > > > 0 2
> > > > > > > > > > 4 6
> > > > > > > > > > ((0,:2),:(2,:2)) (< @: +/ @: ]);.0 i. 4
> > > > > > > > > > +-+-+
> > > > > > > > > > |1|5|
> > > > > > > > > > +-+-+
> > > > > > > > > > (0,:2) (< @: (\:~) @: ]);.0 i. 4
> > > > > > > > > > +---+
> > > > > > > > > > |1 0|
> > > > > > > > > > +---+
> > > > > > > > > > ((0,:2),:(2,:2)) (] @: (\:~) @: ]);.0 i. 4
> > > > > > > > > > 1 0
> > > > > > > > > > 3 2
> > > > > > > > > > ((0,:2),:(2,:2)) (< @: (\:~));.0 i. 4
> > > > > > > > > > +---+---+
> > > > > > > > > > |1 0|3 2|
> > > > > > > > > > +---+---+
> > > > > > > > > >
> > > > > > > > > >
> > > > > > > > > > While "why would you want to use the ']' here?" would be reasonable
> > > > > > to
> > > > > > > > ask,
> > > > > > > > > > but, in the end, syntax is either correct or not. In fact,
I was
> > > > > > > testing
> > > > > > > > > > all kinds of different constructs investigating why
multi-threaded
> > > > > > > > > > operation (with "t.") on subarrays is so much slower than
expected,
> > > > > > > > > > although it's perhaps totally unrelated to what's
discovered above.
> > > > > > > > > >
> > > > > > > > > > Best regards,
> > > > > > > > > > Vadim
> > > > > > > > > >
> > > > > > ----------------------------------------------------------------------
> > > > > > > > > > For information about J forums see
> > > > > > http://www.jsoftware.com/forums.htm
> > > > ----------------------------------------------------------------------
> > > > > > > > > For information about J forums see
> > > > > > http://www.jsoftware.com/forums.htm
> > > > > > > >
----------------------------------------------------------------------
> > > > > > > > For information about J forums see
> > > > http://www.jsoftware.com/forums.htm
> > > > > > >
----------------------------------------------------------------------
> > > > > > > For information about J forums see
http://www.jsoftware.com/forums.htm
> > > > > > >
> > > > > > ----------------------------------------------------------------------
> > > > > > For information about J forums see
http://www.jsoftware.com/forums.htm
> > > > > >
> > > > > ----------------------------------------------------------------------
> > > > > For information about J forums see http://www.jsoftware.com/forums.htm
> > > > ----------------------------------------------------------------------
> > > > For information about J forums see http://www.jsoftware.com/forums.htm
> > > >
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
