BaCon string performance

[Pjot]

Folks,

For fun I created a very simple benchmark to see the differences between BaCon and other languages. It is a program which simply concatenates a character to a string and performs this action 20,000 times.

I have used the following 10 languages:

• Awk
• BaCon
• BASH
• FreePascal
• KSH93
• MKSH
• PDKSH
• Perl
• Python
• Zshell

From these the results for BASH, MKSH, PDKSH and ZSH were too slow to fit in a diagram, so I have left them out. The resulting 6 languages can be observed in the performance graphic below, where it is visible that BaCon takes a poor 5th position

Of course BaCon has the concept of 'memory streams', which allows fiddling with strings directly using POKE and PEEK. And creating a string of 20,000 characters can be achieved using FILL$ also.

But generally, it is strange that similar programs show such different results. Some homework to do here

For your reference the actual programs below.

BR
Peter


BASH:

#!/usr/bin/env bash

BLA=""

for i in `seq 1 20000`
do
   BLA="${BLA}@"
done

echo -n "BASH "


KSH/MKSH/PDKSH/ZSH:

#!/usr/bin/env ksh

BLA=""

for i in `seq 1 20000`
do
   BLA="${BLA}@"
done

print -n "KSH93 "


AWK:

#!/usr/bin/awk -f

BEGIN {
 BLA=""
 for(i=0; i<20000; i++) BLA=BLA"@";
 printf "Awk "
}


Perl:

#!/usr/bin/env perl

$bla = "";

foreach my $i (1..20000) { $bla = $bla . "@"; }

print "Perl "


Python:

#!/usr/bin/env python

import sys

BLA = "";

for x in range(0, 20000):
   BLA = BLA + "@";

sys.stdout.write('Python ')


Pascal:

Program Bench;

{ Program to benchmark string concatenation. }
Var
 BLA : AnsiString;
 i : Integer;

begin
 BLA:='';
 for i := 1 to 20000 do
 begin
   BLA:=Concat(BLA, '@');
 end;
 Write('FreePascal ');
end.


BaCon:

BLA$ = ""

FOR i = 1 TO 20000
   BLA$ = BLA$ & "@"
NEXT

PRINT "BaCon ";


Attachments:

[vovchik]

Dear Peter,

Those guys working on FreePascal have done something very efficient. If my memory serves me right, strings in Pascal are basically arrays of char with the zeroeth element being the length. What do they do with concatenation that makes it fly?

With kind regards,
vovchik

[Deleted]

Peter,

Do you no longer have a copy of Script BASIC on your system?

jrs@laptop:~/BaCon/3.0.2$ time ./strbench

real 0m0.076s
user 0m0.074s
sys 0m0.004s
jrs@laptop:~/BaCon/3.0.2$


BLA$ = ""

FOR i = 1 TO 20000
BLA$ = BLA$ & "@"
NEXT

PRINT "Script BASIC\n"


jrs@laptop:~/sb/sb22/test$ time scriba strbench2.sb
Script BASIC

real 0m0.354s
user 0m0.298s
sys 0m0.004s
jrs@laptop:~/sb/sb22/test$


DIM BLA$ AS STRING
DIM i AS INTEGER

WHILE i <= 20000
 BLA$ = BLA$ & "@"
 i = i + 1
WEND

PRINT "BASM"


jrs@laptop:~/BASM64-MASTER/test$ time ./strbench
BASM

real 0m0.206s
user 0m0.071s
sys 0m0.000s
jrs@laptop:~/BASM64-MASTER/test$


Curious why you have a PRINT that never gets printed in the BaCon version.

[Deleted]

I was wondering what Peter might have done to obtain his new found string management speed. The first clue was I couldn't get BaCon to print anything after the string build loop. I wanted to make sure the concatenated string was the proper length. I added another PRINT with the hopes of seeing some results and my efforts returned a seg fault.


BLA$ = ""

FOR i = 1 TO 20000
BLA$ = BLA$ & "@"
NEXT

PRINT "|" & LEN(BLA$) & "|"
PRINT


jrs@laptop:~/BaCon/3.0.2$ bacon strbench.bac
Converting 'strbench.bac'... done, 7 lines were processed in 0.004 seconds.
Compiling 'strbench.bac'... cc -c strbench.bac.c
cc -o strbench strbench.bac.o -lbacon -lm -ldl
Done, program 'strbench' ready.
jrs@laptop:~/BaCon/3.0.2$ time ./strbench
Segmentation fault (core dumped)

real 0m0.304s
user 0m0.067s
sys 0m0.004s
jrs@laptop:~/BaCon/3.0.2$

[alexfish]

HI John

LEN of String Return Number ,

can not concat a number into CONCAT(strings)

can try STR$ which converts number to string

BLA$ = ""

FOR i = 1 TO 20000
BLA$ = BLA$ & "@"
NEXT

PRINT "|" & STR$(LEN(BLA$)) & "|"
PRINT

HTH
Alex

[Deleted]

Thanks Alex!

jrs@laptop:~/BaCon/3.0.2$ time ./strbench
20000

real 0m0.077s
user 0m0.076s
sys 0m0.000s
jrs@laptop:~/BaCon/3.0.2$

[Pjot]

All,

Last days I have been investigating how the performance of BaCon strings could be improved.

There are several approaches, but it usually comes down to administrating memory size and string size. There are many ways to do this, but the only backwards compatible way seems to be adding some bytes behind the memory block, which contain the block and string size.

Some preliminary experiments with such a setup reveals an average performance gain of approx. 7%. As it is a lot of work to change the string setup in all places in the BaCon code, such a minor performance improvement does not seem worth the effort.

Then the conclusion is that implementing high performance strings has to be done in a non-compatible way. As a POC, I have used Paul Hsieh's "Better String Library", and created a similar test program using this API. The resulting performance of this program is very impressive, even faster than FreePascal's rate!

But first of all, how would the test program look like in native BaCon code using memory streams?

OPTION MEMSTREAM TRUE

mchunk = MEMORY(21000)

FOR i = 1 TO 20000
POKE mchunk+i-1, ASC("@")
NEXT

OPEN mchunk FOR MEMORY AS myvar$

PRINT LEN(myvar$)

If we measure the resulting binary then the average performance of this program is 0.026 seconds. This already is quite good. The resulting variable 'myvar$' can be used in existing string functions like LEN, LEFT$, MID$ etc.

Now we're going to use the Better String Library:

OPTION PARSE FALSE

PRAGMA INCLUDE bstrlib.h bstrlib.c

DECLARE myvar TYPE bstring

myvar = bfromcstr("")

FOR i = 1 TO 20000
bcatcstr(myvar, "@")
NEXT

PRINT blength(myvar)

PRINT "BaCon ";

The average performance of this program is even faster - it shows 0.004 seconds - awesome!

The downside is its incompatibility with the standard BaCon string functions. However, the Better String Library has its own string functions, but also provides functions to convert between the BString type and the standard C string type (for example 'bfromcstr' to convert from C to bstring, and 'bstr2cstr' to do the reverse), allowing interaction with the BaCon string functions.

HTH
Peter

[Deleted]

Peter,

The Better String Library looks great! Thanks for the link and sharing. I might use it for the C BASIC project. The BASM String.inc C functions would give me the string manipulation functions I would need.

My vote is to offer BSL as a high level wrapped library like HUG for BaCon.

John

[alexfish]

Hi All , thought would test Elm lib , here on really need LibEina

INCLUDE hug_elm.bac
PROTO Eina_Strbuf , eina_init ,eina_strbuf_new,eina_strbuf_free,eina_shutdown,eina_strbuf_append
DECLARE *buf TYPE Eina_Strbuf
LOCAL s TYPE int

  eina_init()
  buf = eina_strbuf_new()
s=TIMER
FOR t = 1 TO 20000
  eina_strbuf_append(buf,"@")
 NEXT
PRINT (TIMER - s) , " MSec"

A$=""
s=TIMER
FOR t = 1 TO 20000
  A$=A$&"@"
 NEXT
PRINT "BaCon : " , (TIMER - s) , " MSec"
  eina_strbuf_free(buf)
  eina_shutdown()

Results
./append
2 MSec
BaCon : 738 MSec

= to 0.002
= to 0.738

on a lowly atom
alexfish@alexfish:~/Desktop/hugelm4$

[Pjot]

All,

Our forum member vovchik pointed me to the Simple Dynamic Strings implementation.

I created the following program on my Android tablet:

OPTION PARSE FALSE

PRAGMA INCLUDE sds.h sds.c

DECLARE myvar TYPE sds

myvar = sdsnew("")

FOR i = 1 TO 20000
       myvar=sdscat(myvar, "@")
NEXT

PRINT sdslen(myvar)
PRINT "BaCon ";

After compiling and execution:

terminal++@192.168.16.210:~/BaCon$ bacon bench2
Converting 'bench2.bac'... done, 14 lines were processed in 0.016 seconds.
Compiling 'bench2.bac'... terminal-gcc -fPIC -c bench2.bac.c
terminal-gcc -o bench2 bench2.bac.o -lbacon -lm -ldl
Done, program 'bench2' ready.
terminal++@192.168.16.210:~/BaCon$ time ./bench2
20000
BaCon
real 0m0.005s
user 0m0.000s
sys 0m0.000s
terminal++@192.168.16.210:~/BaCon$

Even on my Android tablet, the performance of string concatenation is outstanding! And the big advantage of the SDS implementation is its backwards compatibility with regular C strings.

Thanks vovchik for pointing to this.

BR
Peter

[alexfish]

@ Vovchik & Peter

Just Tested this one on Intel atom , time is same

real  0m0.005s

all I can say,

Re Bacon code + sds + Android timings
+ simple API of sds,

Speak Volumes in its self

Though can see the real benefit on portability and can use standard c print*

Thanks Vovchik..

[vovchik]

Dear Peter and Alex,

Thanks - I was just lucky in locating this one. It also rips on my Intel(R) Atom 2.13GHz, taking all of 0.003s, which is over 100x faster than the standard method (0.417s). I think we are onto something good and useful.

With kind regards,
vovchik

[alexfish]

Hi All
Looks like can just allocate as normal char* but can not perform any of the functions on the string
more or less in line with same as actions of same char* = segfault

may be worth looking further.

sds got_it
got_it = " hello world "
PRINT got_it
got_it = " hello world 2"
PRINT got_it

sds get_it = "FooBar"

and so on

Update :: ran a mixed bag on this one with the above , as in the mixed bag/ valgrind results

==5019== HEAP SUMMARY:
==5019== in use at exit: 0 bytes in 0 blocks
==5019== total heap usage: 5 allocs, 5 frees, 552 bytes allocated
==5019==
==5019== All heap blocks were freed -- no leaks are possible

Br
Alex

[vovchik]

Dear Alex,

It works OK this way:


OPTION PARSE FALSE
PRAGMA INCLUDE sds.h sds.c
PROTO printf
DECLARE got_it, get_it TYPE sds
got_it = sdsnew("")
get_it = sdsnew("")
got_it = " hello world "
printf("%s\n", got_it)
got_it = " hello world 2"
printf("%s\n", got_it)
get_it = "FooBar"
printf("%s\n", get_it)


So, if it is integrated into BaCon, PRINT will have to be modded to accept that type or we run a conversion on the "*char" type to make it like a BaCon string for purposes of PRINT. Or, perhaps, Peter might just want to take the sds_concat bit.

With kind regards,
vovchik

PS. This also works:


OPTION PARSE FALSE
PRAGMA INCLUDE sds.h sds.c
PROTO printf
PROTO sprintf
DECLARE got_it, get_it TYPE sds
DECLARE x$ TYPE STRING
x$ = " hello world "
got_it = sdsnew(x$)
get_it = sdsnew("")
printf("%s\n", got_it)
x$ = "2"
got_it = sdscat(got_it, x$)
printf("%s\n", got_it)
get_it = "FooBar"
printf("%s\n", get_it)
sprintf(x$, "%s", got_it)
PRINT x$
x$ = CHOP$(x$)
PRINT LEN(x$)
PRINT MID$(x$, 4, 3)


[vovchik]

Dear Peter and Alex,

What about something like this?

OPTION PARSE FALSE
PRAGMA INCLUDE sds.h sds.c
DECLARE newstring$ TYPE STRING

' ------------------
FUNCTION SDSCAT$((VAR arg$ SIZE amount)
' ------------------
LOCAL xx TYPE int
LOCAL st$ TYPE STRING
LOCAL mystring TYPE sds
st$ = ""
mystring = sdsnew("")
FOR xx = 0 TO amount - 1
mystring = sdscat(mystring, arg$[xx])
NEXT xx
st$ = (char*)mystring
sdsclear(mystring)
RETURN st$
END FUNCTION


newstring$ = SDSCAT$("How ", "are ", "you?")
PRINT newstring$
newstring$ = SDSCAT$("Are ", "your ", "groovy?")
PRINT newstring$
PRINT SDSCAT$("Are ", "you ", "really ", "\"that\" ", "groovy?")

It works fine for me in principle, and I now want to do the speed test....

With kind regards,
vovchik

UPDATE: Did the speed test and it is AWFUL (2.xs), which is much slower than BaCon in the above implementation, so back to the drawing board. We have to find a more clever way....

UPDATE1: Did some speed tests - see attached archive. It is much faster if implemented correctly. I am working on that now....