RaspberryBASIC.org Forum

[John]

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 $

[AIR]

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.

[John]

Judy Array C Library

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

SB arrays are dynamic linked lists.

[jalih]

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.

[jalih]

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!

[John]

The keyword is dynamic.

[AIR]

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.

[jalih]

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!

[John]

C finally leads the pack.

Nice job!

[AIR]

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.

[John]

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.

[jalih]

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.

[John]

That sounds acceptable to me.

[AIR]

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.

[AIR]

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.