Tatami Pi Fun.

[jahboater]

I might say that having multiple threads makes no difference. When your recursion is too much you are going to die of stack overflow no matter if it just one thread running or many. The only question is when does that happen?

What about this:

-fsplit-stack
Generate code to automatically split the stack before it overflows. The resulting
program has a discontiguous stack which can only overflow if the program is unable to
allocate any more memory. This is most useful when running threaded programs, as it
is no longer necessary to calculate a good stack size to use for each thread. This is
currently only implemented for the x86 targets running GNU/Linux.

[jahboater]

Heater,

There are many options for stack protection:

Code: Select all

 -fstack-protector
     Emit extra code to check for buffer overflows, such as stack smashing attacks.  This
     is done by adding a guard variable to functions with vulnerable objects.  This
     includes functions that call "alloca", and functions with buffers larger than 8 bytes.
     The guards are initialized when a function is entered and then checked when the
     function exits.  If a guard check fails, an error message is printed and the program
     exits.

 -fstack-protector-all
     Like -fstack-protector except that all functions are protected.

 -fstack-protector-strong
     Like -fstack-protector but includes additional functions to be protected --- those
     that have local array definitions, or have references to local frame addresses.

-fstack-protector-explicit
    Like -fstack-protector but only protects those functions which have the
   "stack_protect" attribute.

Also importantly:

Code: Select all

-fstack-check
     Generate code to verify that you do not go beyond the boundary of the stack.  You
     should specify this flag if you are running in an environment with multiple threads,
     but you only rarely need to specify it in a single-threaded environment since stack
     overflow is automatically detected on nearly all systems if there is only one stack.

     Note that this switch does not actually cause checking to be done; the operating
     system or the language runtime must do that.  The switch causes generation of code to
     ensure that they see the stack being extended.

     You can additionally specify a string parameter: no means no checking, generic means
     force the use of old-style checking, specific means use the best checking method and
     is equivalent to bare -fstack-check.

    -fstack-check= is designed for Ada's needs to detect infinite recursion and stack
      overflows.  specific is an excellent choice when compiling Ada code.  It is not
      generally sufficient to protect against stack-clash attacks.  To protect against those
      you want -fstack-clash-protection.

     Old-style checking is a generic mechanism that requires no specific target support in
     the compiler but comes with the following drawbacks:

     1.  Modified allocation strategy for large objects: they are always allocated
          dynamically if their size exceeds a fixed threshold.  Note this may change the
          semantics of some code.

    2.  Fixed limit on the size of the static frame of functions: when it is topped by a
         particular function, stack checking is not reliable and a warning is issued by the
         compiler.

     3.  Inefficiency: because of both the modified allocation strategy and the generic
          implementation, code performance is hampered.

     Note that old-style stack checking is also the fallback method for specific if no
     target support has been added in the compiler.

 -fstack-clash-protection
     Generate code to prevent stack clash style attacks.  When this option is enabled, the
     compiler will only allocate one page of stack space at a time and each page is
     accessed immediately after allocation.  Thus, it prevents allocations from jumping
     over any stack guard page provided by the operating system.

     Most targets do not fully support stack clash protection.  However, on those targets
     -fstack-clash-protection will protect dynamic stack allocations.
     -fstack-clash-protection may also provide limited protection for static stack
     allocations if the target supports -fstack-check=specific.

[ejolson]

Got bored. Started to marvel at the cabbage patch.

From the logarithmic cabbage patch, one can see that tatami-challenge entries with more lines of code run faster than those with less. This observation creates a paradox in direct contradiction with everyday computing experience where it is well known that code bloat causes spreadsheets, word processors and operating systems to run slower.

As is the fashion with each passing year, we look back over 2019 to determine whether there has been any increase in computer literacy. If computer literacy is increasing, it should follow that fewer questions need to be asked on this forum. This, in turn, means that each year should consist of fewer new posts. Upon checking the current statistics reported on the main page we note that

Code: Select all

Date           Total Posts
Jan 3, 2019    1333273
Jan 2, 2020    1515329

Therefore, 182056 new posts were made to the Raspberry Pi Forum during the year 2019. Combining this data with last year's analysis

https://www.raspberrypi.org/forums/view ... 0#p1427911

leads to



In particular, the number of new posts in 2019 was greater compared to 2017 and 2018--a result which suggests confusion about how computers work is again on the rise. In fact, the posting rate is back to where things started in 2014. According to the head of marketing and communication, the only way to avoid the digital apocalypse indicated by this alarming change in trend is for more people to solve tatami challenges.

On the other hand, maybe the increased posting rate was a result of enthusiasm over the release of the Raspberry Pi 4B.

[Heater]

jahboater,

Wow, all those fstack things seem like a great idea. Apparently I missed the memo when they were created.

Seems they are nothing to do with the C language though. As far as I can tell they are compiler extensions that only work with the right compiler, on x86.

Which of course raises the question: How much of that Rust language stack checking is mandated by the Rust language itself. And how much is an accident of the OS it runs on?

[Heater]

ejolson,

In particular, the number of new posts in 2019 was greater compared to 2017 and 2018, which means computer illiteracy is again on the rise. In fact, the posting rate is back to where things started in 2014.

So you are saying nothing much has changed in 5 years?

Computer literacy is still almost non-existent in the general population.

As is evidenced by the way people offer up every detail of their life, including their DNA, to whatever fly by night web service comes along.

I despair....

[ejolson]

ejolson,

In particular, the number of new posts in 2019 was greater compared to 2017 and 2018, which means computer illiteracy is again on the rise. In fact, the posting rate is back to where things started in 2014.

So you are saying nothing much has changed in 5 years?

Computer literacy is still almost non-existent in the general population.

As is evidenced by the way people offer up every detail of their life, including their DNA, to whatever fly by night web service comes along.

I despair....

As the peasants of the past traded freedom and cabbage for the convenience of being protected by the landlord who owned the castle on the hill, so the digital peasants of this age are more focused on convenience than liberty or the accumulation of cabbages.

At the same time, if the only thing necessary to reverse this trend is some tatami-challenge solutions that don't overflow the stack, then why avoid Basic?

[Heater]

ejolson.

As the peasants of the past traded freedom and cabbage for the convenience of being protected by the landlord who owned the castle on the hill, ...

Oh boy...

The peasants of the past never voluntarily traded freedom and cabbage for the convenience of being protected by the landlord

When I was a young teenager in school, in 1972 or whatever, we had a history class of course. We were informed of the Inclosures Act of 1773. https://en.wikipedia.org/wiki/Inclosure_Acts

There was no "peasants of the past traded freedom and cabbage". No, they had no choice.

I put my hand up in that class and basically said "That was a really shitty thing for the king to do". I was much more polite in those days.

I was branded as a "disturbing influence" in the school ever after. I still have school reports that says so.

As it happens at that time I was living in Canterbury in England. Our house was at the bottom of "Tyler Hill"

Which I found out later was named after Wat Tyler. A peasant who tried to revolt against such things some year before:
https://en.wikipedia.org/wiki/Wat_Tyler

It's hopeless. We have no free will in this modern world. We do what we are told.

[jahboater]

Heater,

Seems they are nothing to do with the C language though. As far as I can tell they are compiler extensions that only work with the right compiler, on x86.

Yes. Except that I think its only the complicated split-stack thing that is x86 specific. I am pretty sure the rest should work on the Pi.

Stack protection is often the default for C (wired in when the compiler is built by the OS maintainers) (e.g. RedHat, CentOS and even Ubuntu at one time).

Which of course raises the question: How much of that Rust language stack checking is mandated by the Rust language itself. And how much is an accident of the OS it runs on?

It may be a switch for LLVM or rustc. I don't know.
C by default segfaults which is what the OS does, whereas rust produces an informative message. So its either catching SIGSEGV or some kind of compiler produced checking code is in place.
Interesting!

[Heater]

jahboater,

I think we are taking at cross purposes here.

What if we are not using GCC or Clang/LLVM? There are many other C compilers out there. For many architectures besides Intel an ARM.

As far as I can tell the reason why the C/C++ standards have so many undefined behaviors is to accommodate all those strange architectures.

As far as I can tell the C/C++ standards say nothing about what should happen if heap or stack memory gets exhausted.

My question now is does the Rust language say anything about that?

[ejolson]

Hoping to turn the page on this Tatami thing with its claimed negative impact on literacy, I present a final version of the original Tatami threaded solution, but in CUDA.

The CUDA program seems similar to thread.cpp from the starchart, which has a runtime of 9.14 seconds. How fast is the CPU code on the Jetson Nano?

It would be nice if the Pi eventually had some sort of CUDA-like programming language for the VC6 GPU. Given that most of the computational performance of top machines like Summit and Sierra come from attached Nvidia GV100 processors, it seems necessary to teach parallel GPU techniques to reach the level of literacy practical for avoiding a digital apocalypse, or at least for solving tatami programming challenges.

[Heater]

Meanwhile in normal CPU land something very weird is going on....

I wanted to do some timing for the big 64 bit Tatami 1000 problem across all the programs we have that can do that. So I fixed up a makefile to build 32 and 64 bit versions of prune.c, pqplum.c and tatami_rust.rs. Also a script to run and time the 64 bit versions.

On my x86_64 this is the result:

$./run64.sh
-------------------------------
Linux monster 4.4.0-17134-Microsoft #706-Microsoft Mon Apr 01 18:13:00 PST 2019 x86_64 GNU/Linux
-------------------------------
prune64
Pr(40000)=479909
./rT(63405342000)=1000

real 4m39.709s
user 4m39.219s
sys 0m0.000s
-------------------------------
pqplum64
T(63405342000)=1000

real 2m3.285s
user 13m49.828s
sys 0m0.203s
-------------------------------
tatami_rust_threaded64.rs
Using 64 bit integers.
PNUM = 40000
FNUM = 20
SMAX = 100000000000
Pr(40000)=479909
Running Rust translation of queue.c...
T(63405342000)=1000

real 1m31.967s
user 11m40.750s
sys 0m0.688s
-------------------------------

Well look at that. Rust and the rayon thread pool library is wiping the board!


But on the Pi 3B everyting goes wrong:

$./run64.sh
-------------------------------
Linux debian-buster-64 4.19.75-v8+ #1270 SMP PREEMPT Tue Sep 24 18:59:17 BST 2019 aarch64 GNU/Linux
-------------------------------
prune64
Pr(40000)=479909
T(63405342000)=1000

real 19m46.191s
user 19m45.901s
sys 0m0.017s
-------------------------------
pqplum64
./run64.sh: line 12: 20616 Segmentation fault

real 0m0.210s
user 0m0.412s
sys 0m0.115s
-------------------------------
tatami_rust_threaded64
Using 64 bit integers.
PNUM = 40000
FNUM = 20
SMAX = 100000000000
Pr(40000)=479909
Running Rust translation of queue.c...
T(63405342000)=1000

real 24m17.314s
user 93m32.503s
sys 0m16.106s
-------------------------------

I can't get pqplum to run at all. Is there a version that sets a bigger thread stack size?

The Rust seems to have decided not to use threads at all!

Edit: Except of course it is using threads, there is 93m of user time reported there. WTF?

https://github.com/ZiCog/tatami-rust

[Heater]

OK. One mystery solved. Sort of.

I reverted my makefile to use GCC instead of Clang. Now pqplum 1000 works:

pqplum64 (C + pthreads)
T(63405342000)=1000

real 13m27.110s
user 49m42.756s
sys 0m1.040s

But perversely the threaded tatami_rust 1000 performs abysmally.

tatami_rust_threaded64 (Rust + rayon)
Using 64 bit integers.
PNUM = 40000
FNUM = 20
SMAX = 100000000000
Pr(40000)=479909
Running Rust translation of queue.c...
Uing 4 cores.
T(63405342000)=1000

real 25m16.258s
user 96m57.495s
sys 0m8.798s

I cannot begin to imagine why that is so bad on ARM when it is so good on x86.

[Heater]

Thinking about it some more...

Looking at the results I'm getting for Tatami 1000 it seems even the C using pthreads is performing very badly. A speed up of only 2.6 when using 8 cores on my PC is nothing to shout about. Rust pushes that to a speed up of 2.9, still not scaling well.

Over on the Pi 3 side C and pthreads is only speeding up by 1.4 for the four cores. And Rust is slowing down by 20%

In summary:

Code: Select all

                                x86_64          ARM(Pi 3B)

prune64 (C, single threaded)    4m47s           19m46s

pqplum64 (C, pthreads)          1m51s           13m27s

tatami_rust_threaded64 (rayon)  1m37s           25m16s

From the x86 results I conclude that this algorithm does not scale well in C or Rust.

From the ARM results I conclude there is something very broken with threads on ARM.

[ejolson]

Thinking about it some more...

Looking at the results I'm getting for Tatami 1000 it seems even the C using pthreads is performing very badly. A speed up of only 2.6 when using 8 cores on my PC is nothing to shout about. Rust pushes that to a speed up of 2.9, still not scaling well.

Over on the Pi 3 side C and pthreads is only speeding up by 1.4 for the four cores. And Rust is slowing down by 20%

In summary:

Code: Select all

                                x86_64          ARM(Pi 3B)

prune64 (C, single threaded)    4m47s           19m46s

pqplum64 (C, pthreads)          1m51s           13m27s

tatami_rust_threaded64 (rayon)  1m37s           25m16s

From the x86 results I conclude that this algorithm does not scale well in C or Rust.

From the ARM results I conclude there is something very broken with threads on ARM.

Cache sizes are much smaller on the Pi, so the problem will scale differently. Also recall that eight Intel hyperthreads equate to only four physical cores.

It's tempting to launch an 8-core Graviton A1 ARM instance on the Amazon EC2 cloud to taste how well the tatami codes might go with future pies. On the other hand, maybe all you need is to turn the fido setting on the powerdog function back up to 15, or at least 11.

How does queue.c work?

Run with something like

$ OMP_STACKSIZE=6M ./queue

where 6M is chosen large enough that the stack overflows go away.

[Heater]

ejolson,

How does queue.c work?

Works fine. Runs as slow as a slow thing on a slow day in Slowville.

Code: Select all

$ gcc -Wall -O3 -fopenmp -o queue queue.c -lm
pi@debian-buster-64:~/tatami-rust $ time ./queue
Using 8 threads.
Pr(40000)=479909

T(63405342000)=1000
Lc=15832

real    24m38.601s
user    92m47.575s
sys     0m10.180s 

So my summary table now looks like:

Code: Select all

                                x86_64          ARM(Pi 3B)

queue64 (OMP)                   1m58s           24m38s

prune64 (C, single threaded)    4m47s           19m46s

pqplum64 (C, pthreads)          1m51s           13m27s

tatami_rust_threaded64 (rayon)  1m37s           25m16s

I don't have a 'fido' parameter but I do have a constant called 'FIFTEEN' conveniently defined to actually be '15.0'.

Is tweaking that likely to change anything?

[ejolson]

ejolson,

How does queue.c work?

Works fine. Runs as slow as a slow thing on a slow day in Slowville.

Code: Select all

$ gcc -Wall -O3 -fopenmp -o queue queue.c -lm
pi@debian-buster-64:~/tatami-rust $ time ./queue
Using 8 threads.
Pr(40000)=479909

T(63405342000)=1000
Lc=15832

real    24m38.601s
user    92m47.575s
sys     0m10.180s 

So my summary table now looks like:

Code: Select all

                                x86_64          ARM(Pi 3B)

queue64 (OMP)                   1m58s           24m38s

prune64 (C, single threaded)    4m47s           19m46s

pqplum64 (C, pthreads)          1m51s           13m27s

tatami_rust_threaded64 (rayon)  1m37s           25m16s

I don't have a 'fido' parameter but I do have a constant called 'FIFTEEN' conveniently defined to actually be '15.0'.

Is tweaking that likely to change anything?

The fido parameter (also conveniently label fifteen) determines the granularity with which the tatami computation is parallelized. I would try optimizing over values between 10 and 20. You can also adjust the value for the sqrt(2) upwards if you are feeling brave. Better might be to remove the powerdog function entirely, but I'm not sure how.

Does cabbage.go compiled with "go build" work better?

I find it surprising, with the exception of pqplum.c, that

• Parallel is slower than serial on the Pi 3B.
• Parallel is faster than serial on your x86.

I smell some rotten cabbage. I wonder what the story is for the 4B.

[Heater]

ejolson,

You can also adjust the value for the sqrt(2) upwards

What? You want me to change the value of the square root of two!

I know Pythagorean's had a problem with root two but I thought you were a mathematician not an alchemist.

Does cabbage.go compiled with "go build" work better?

No idea. I have too many variables to keep track of already. I will not "go" there until a Go solution is top of the cabbage chart. I have seen Go fail miserably many times before.

I find it amusing, with the exception of pqplum.c, that
Parallel is slower than serial on the Pi 3B.
Parallel is faster than serial on your x86.

Yeah.

What is that about?

Just goes to show that in the modern world you cannot tell what performance you get from reading the source code.

[ejolson]

I will not "go" there until a Go solution is top of the cabbage chart. I have seen Go fail miserably many times before.

I get the following on a 1920X 12-core Threadripper.

Code: Select all

$ OMP_STACKSIZE=6M /usr/bin/time ./queue
Pr(40000)=479909
T(63405342000)=1000
Lc=16385
478.25user 0.10system 0:24.22elapsed 1974%CPU (0avgtext+0avgdata 152688maxresident)k
0inputs+0outputs (0major+37999minor)pagefaults 0swaps
$ /usr/bin/time ./cabbage
P[40000]=479909
T(63405342000)=1000
329.62user 0.07system 0:31.74elapsed 1038%CPU (0avgtext+0avgdata 48648maxresident)k
0inputs+0outputs (0major+11702minor)pagefaults 0swaps

There is a possibility of further tuning that might be done with cabbage.go, because at only 1038% CPU it's not parallelizing efficiently to all the cores.

[Heater]

ejolson,

...at only 1038% CPU it's not parallelizing efficiently to all the cores.

I have come to the conclusion that watching the percent CPU used is not a good measure of scaling efficiency.

For example when queue.c is running slowly on a slow day in Slowville we see the run time is 24m38s and the CPU time is 92m47s. We have 3.8 times more work going on across all the cores.

That looks great. Makes it look like we are 'efficiently' using all the cores, that is nearly the 400% we would like to see.

But the actual run time is slower than the single threaded solution. We are just making heat on those 3 other cores!

[ejolson]

But the actual run time is slower than the single threaded solution. We are just making heat on those 3 other cores!

One can compile queue.c to run single threaded by simply omitting the

-fopenmp

flag. The conclusion appears to me that the slowness in Slowville is more related to the powerdog function than anything else. More information is available at

https://www.raspberrypi.org/forums/view ... 0#p1574367

[Heater]

ejolson,

One can compile queue.c to run single threaded by simply omitting the

OK. Then I get the following results for queue.c

Code: Select all

Machine     Threads     Time
x86_64      2           8m9s
x86_64      16          1m59s
Pi 3B       2           38m19
Pi 3B       8           24m15

That is a speed up of 4 on the PC but only 1.6 on the Pi.

If we ignore hyperthreading we could say that is perfect scaling across 4 cores on the PC.

But it is abysmal on the Pi's 4 cores.

...slowness in Slowville is more related to the powerdog function than anything else. More information is available at...

I did not get anything from that link except the relative cost of dog treats and gasoline.

[ejolson]

ejolson,

One can compile queue.c to run single threaded by simply omitting the

OK. Then I get the following results for queue.c

Code: Select all

Machine     Threads     Time
x86_64      2           8m9s
x86_64      16          1m59s
Pi 3B       2           38m19
Pi 3B       8           24m15

That is a speed up of 4 on the PC but only 1.6 on the Pi.

I've been thinking about these results. Is it possible the Pi is throttling due to low voltage or excess heat when all four cores are active?

[Heater]

I was wondering about that when I wrote the post.

I had been watching the cpu_freq in /sys/... or wherever it is. It just said 120000 all the time. Running code or not.

However there were bits set in the get_throttling of vcgencmd.

I have to set myself up with a nicely cooled Turbo Encabulator....

[PeterO]

I have to set myself up with a nicely cooled Turbo Encabulator....

https://www.youtube.com/watch?v=u4ILnWpi8XY

[ejolson]

I have to set myself up with a nicely cooled Turbo Encabulator....

https://www.youtube.com/watch?v=u4ILnWpi8XY

It looks like plans for building a micro encabulator complete with source code, schematic, Gerber files and a BOM is described in the post

https://www.raspberrypi.org/forums/view ... 8#p1590548

For me the questions that remain are how to ensure getting revision 1.2 with fast-charger compatible USB-C power and if the variable-speed micro-induction ports will overheat when processing material manufactured in thin sheets from the pulp of wood or other fibrous substances, not to mention dog hair.

Merry Christmas!