Author Topic: RaspberryBASIC.org Forum  (Read 16921 times)

Offline John

  • Forum Support / SB Dev
  • Posts: 2969
    • ScriptBasic Open Source Project
Re: RaspberryBASIC.org Forum
« Reply #105 on: December 08, 2019, 04:25:05 PM »
Here is some interesting info about ScriptBasic array memory usage. I remarked out the array code. I really need to get the Judy extension module built.


pi@RPi4B:~/sbrt/examples $ timex scriba 1milsf.sb
t LEN: 999986
Front: ZYXWVUTSRQPONMLKJIHGFEDCBA
Back:  ZYXWVUTSRQPONMLKJIHGFEDCBA
5.26user 0.29system 0:05.58elapsed 99%CPU (0avgtext+0avgdata 3696maxresident)k
272inputs+1968outputs (0major+846minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $


With Array


pi@RPi4B:~/sbrt/examples $ timex scriba 1milsf.sb
t LEN: 999986
Front: ZYXWVUTSRQPONMLKJIHGFEDCBA
Back:  ZYXWVUTSRQPONMLKJIHGFEDCBA
UBVal: 1000000
7.03user 0.84system 0:07.89elapsed 99%CPU (0avgtext+0avgdata 171504maxresident)k
0inputs+1976outputs (0major+43080minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $


I thought I would give the Linux memory drive device (/dev/shm) a try with ScriptBasic. It seems the SD drive is just as fast.


pi@RPi4B:~/sbrt/examples $ timex scriba 1milsf.sb
t LEN: 999986
Front: ZYXWVUTSRQPONMLKJIHGFEDCBA
Back:  ZYXWVUTSRQPONMLKJIHGFEDCBA
UBVal: 1000000
7.05user 0.47system 0:07.52elapsed 99%CPU (0avgtext+0avgdata 171472maxresident)k
0inputs+0outputs (0major+43081minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $


« Last Edit: December 08, 2019, 05:41:29 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 782
Re: RaspberryBASIC.org Forum
« Reply #106 on: December 08, 2019, 06:10:38 PM »
It's not storage I/O, I think you're seeing the effect that Jalih was referring to, the fact that in most higher level languages strings are immutable by default.

So (potentially) the slowness is due to new strings being allocated to address the fact that the space the current string holds is not large enough for the concatenation. Then the current string's contents need to be copied over to the newly allocated string along with whatever you're trying to add.


This is even more noticeable is SB because essentially every object is a string.  I'm guessing that this is the reason for the higher than normal memory usage this challenge is showing for the SB submissions.

BTW, what's Judy?

AIR.

Offline John

  • Forum Support / SB Dev
  • Posts: 2969
    • ScriptBasic Open Source Project
Re: RaspberryBASIC.org Forum
« Reply #107 on: December 08, 2019, 06:18:45 PM »
Judy Array C Library

SB"s variables are variant based. Flexible but costly to performace.

SB arrays are dynamic linked lists.
« Last Edit: December 08, 2019, 06:34:42 PM by John »

Offline jalih

  • Advocate
  • Posts: 89
Re: RaspberryBASIC.org Forum
« Reply #108 on: December 08, 2019, 08:51:19 PM »
I'm waiting for Jalih to show us a 8th submission that lives within the generous rules stated. Exposed buffer code will surely get you busted.

I will soon post version with fully featured string builder that can dynamically grow ascii character buffers, if need to. If you accept other entrys using string builders, then you must accept my 8th version.

Offline jalih

  • Advocate
  • Posts: 89
Re: RaspberryBASIC.org Forum
« Reply #109 on: December 08, 2019, 08:54:13 PM »
BTW, your 8th submission only runs 1 out of 4 times on my system; the error is the same as before.

Have to boot up my ROCK64, add some debug code and see why! On Windows, it works every time!

Offline John

  • Forum Support / SB Dev
  • Posts: 2969
    • ScriptBasic Open Source Project
Re: RaspberryBASIC.org Forum
« Reply #110 on: December 08, 2019, 09:14:04 PM »
The keyword is dynamic.

Offline AIR

  • BASIC Developer
  • Posts: 782
Re: RaspberryBASIC.org Forum
« Reply #111 on: December 08, 2019, 10:06:54 PM »
Was wondering how this would look if I used GLIB:

Code: C
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <glib.h>
  4. #include <glib/gprintf.h>
  5.  
  6. int main(int argc, char **argv) {
  7.         GString *s = g_string_new(NULL);
  8.         GString *t = g_string_new(NULL);
  9.         int a[1000001] = {0};
  10.  
  11.         for (int x = 0; x < 1000001; x++) {
  12.                 a[x] = x;
  13.                 g_string_append_c(s,(char)(x%26)+65);
  14.                 if (s->len == 26) {
  15.                         g_string_append(t,g_strreverse(s->str));
  16.                         g_string_assign(s,"");
  17.                 }
  18.         }
  19.  
  20.         g_printf("r LEN: %d\n",t->len);
  21.         g_printf("Front: %.*s\n", 26, t->str);
  22.         g_printf("Back:  %s\n", t->str + t->len - 26);
  23.         g_printf("UBVal: %d\n",a[1000000]);
  24.  
  25.         g_string_free (s,TRUE);
  26.         g_string_free (t,TRUE);
  27. }

riveraa@rpi:~/Projects/glib $ gcc -O3 mil.c  $(pkg-config --libs --cflags glib-2.0) -o mil
riveraa@rpi:~/Projects/glib $ timex ./mil
r LEN: 999986
Front: ZYXWVUTSRQPONMLKJIHGFEDCBA
Back:  ZYXWVUTSRQPONMLKJIHGFEDCBA
UBVal: 1000000
0.04user 0.02system 0:00.07elapsed 98%CPU (0avgtext+0avgdata 6384maxresident)k
0inputs+0outputs (0major+1334minor)pagefaults 0swaps


AIR.

Offline jalih

  • Advocate
  • Posts: 89
Re: RaspberryBASIC.org Forum
« Reply #112 on: December 08, 2019, 10:44:41 PM »
The keyword is dynamic.
All the fast entries here don't use immutable strings. They use buffer that can grow, if needed! Less allocations and copying stuff around makes program faster! You can set the size for Go's string builders internal slice, so no new memory allocations and unnecessary copying is needed!

Offline John

  • Forum Support / SB Dev
  • Posts: 2969
    • ScriptBasic Open Source Project
Re: RaspberryBASIC.org Forum
« Reply #113 on: December 09, 2019, 06:48:42 AM »
C finally leads the pack.

Nice job!
« Last Edit: December 09, 2019, 07:32:55 AM by John »

Offline AIR

  • BASIC Developer
  • Posts: 782
Re: RaspberryBASIC.org Forum
« Reply #114 on: December 09, 2019, 08:53:14 AM »
The keyword is dynamic.
All the fast entries here don't use immutable strings. They use buffer that can grow, if needed! Less allocations and copying stuff around makes program faster! You can set the size for Go's string builders internal slice, so no new memory allocations and unnecessary copying is needed!

Pre-allocating the buffer would be the most efficient way to do this, of course.  But as we've seen with multiple submissions, not pre-allocating the space highlights the issues with immutable strings which you've pointed out.  This challenge is interesting in that it forces us to come up with alternative approaches to string handling that could be used when the size of strings is unknown, while hopefully maintaining decent overall performance.

My submissions using the open_memstream function is a good example; I didn't even know this function existed prior to this challenge.  So I learned something new!

AIR.

Offline John

  • Forum Support / SB Dev
  • Posts: 2969
    • ScriptBasic Open Source Project
Re: RaspberryBASIC.org Forum
« Reply #115 on: December 09, 2019, 09:00:20 AM »
This challenge highlighted ScriptBasic's performance penalties and excessive memory using its strings and arrays. The challenge made me see that there are better solutions without a huge learning curve.

Offline jalih

  • Advocate
  • Posts: 89
Re: RaspberryBASIC.org Forum
« Reply #116 on: December 09, 2019, 09:18:07 AM »
Pre-allocating the buffer would be the most efficient way to do this, of course.  But as we've seen with multiple submissions, not pre-allocating the space highlights the issues with immutable strings which you've pointed out.  This challenge is interesting in that it forces us to come up with alternative approaches to string handling that could be used when the size of strings is unknown, while hopefully maintaining decent overall performance.
My point was that all the really fast versions here use pre-allocated buffer under the cover to store the string and grow the buffer some amount only, if needed. Go's string builder does that as well as GString. Not sure about the default allocated buffer sizes, but it makes sense to minimize allocations and copying. My current 8th version (not posted yet) uses buffer to store ascii string bytes and that buffer can dynamically grow, if needed.

Offline John

  • Forum Support / SB Dev
  • Posts: 2969
    • ScriptBasic Open Source Project
Re: RaspberryBASIC.org Forum
« Reply #117 on: December 09, 2019, 09:52:06 AM »
That sounds acceptable to me.

Offline AIR

  • BASIC Developer
  • Posts: 782
Re: RaspberryBASIC.org Forum
« Reply #118 on: December 09, 2019, 10:11:35 AM »
My point was that all the really fast versions here use pre-allocated buffer under the cover to store the string and grow the buffer some amount only, if needed. Go's string builder does that as well as GString. Not sure about the default allocated buffer sizes, but it makes sense to minimize allocations and copying. My current 8th version (not posted yet) uses buffer to store ascii string bytes and that buffer can dynamically grow, if needed.

Well, yes.  You shouldn't assign to a char*, for example, unless you've allocated enouch space for it. 


I think the wording is what is confusing things;  what I mean by pre-allocated buffer is a STATIC buffer, for example char a[65535].  You can't call "realloc' on that, so you have to create a new string if you want to 'add' to it.

So now the question becomes, what is a 'fair' initial buffer size.  'g_string_new(NULL)', which is what I used in the GLIB submission, creates an initial buffer that is 2 bytes in size (according to the source code for GString).  I could have passed an initial size, like the 65K above, but I wanted to test how the default operated from a performance standpoint.


Anyway, I'm looking forward to seeing how you choose to implement this, Jalih.

AIR.

Offline AIR

  • BASIC Developer
  • Posts: 782
Re: RaspberryBASIC.org Forum
« Reply #119 on: December 09, 2019, 10:20:51 AM »
Had a few minutes, decided to try a Ruby version

Code: Ruby
  1. #!/usr/bin/ruby
  2.  
  3. a = [10000001]
  4. s = ""
  5. t = ""
  6.  
  7.  
  8. (0..1000001).each do |x|
  9.         a << x+1
  10.         s << (x%26)+65
  11.         if s.length == 26
  12.                 t << s.reverse
  13.                 s.clear
  14.         end
  15. end
  16.  
  17. puts "r LEN: #{t.length}"
  18. puts "Front: #{t[0,26]}"
  19. puts "Back:  #{t[-26,26]}"
  20. puts "UBVal: #{a[1000000]}"
  21.  

riveraa@rpi:~/Projects/ruby $ timex ./mil.rb .
r LEN: 999986
Front: ZYXWVUTSRQPONMLKJIHGFEDCBA
Back:  ZYXWVUTSRQPONMLKJIHGFEDCBA
UBVal: 1000000
0.89user 0.03system 0:00.93elapsed 99%CPU (0avgtext+0avgdata 12084maxresident)k
0inputs+0outputs (0major+2161minor)pagefaults 0swaps


AIR.