FAST bank to string

This code has been declared by its author to be Public Domain code.

FAST bank to string by Yasha

2012

It's not difficult to copy data between bank and string in pure Blitz Basic. Just loop over the characters or bytes and either poke ascii values, or append the new Chr() to the build-string.

Unfortunately, it is really, really slow, due to the automatic string memory management behind the scenes having to do a lot of copying, reallocation, etc.

However, with not one but two dirty tricks, we can use the system runtime libraries to do the hard work for us, resulting in a pair of copy functions something ridiculous like fifty times faster than doing it by hand. This could come in very, very handy when looping over all of the characters in a string!

Here's a speed comparison:

Const ITNS = 100000
Local start, i, r
Local f$ = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", s$, bk

start = MilliSecs()
For i = 1 To ITNS
	bk = StringToBank_FAST(f)
	s = BankToString_FAST(bk)
	FreeBank bk
Next
start = MilliSecs() - start : Print "Fast copy: " + start

Print s

start = MilliSecs()
For i = 1 To ITNS
	bk = StringToBank_SLOW(f)
	s = BankToString_SLOW(bk)
	FreeBank bk
Next
start = MilliSecs() - start : Print "Slow copy: " + start


WaitKey
End


Function StringToBank_FAST(s$)
	Local b = CreateBank(Len(s))
	API_StringToBank_ b, s, BankSize(b)
	Return b
End Function

Function BankToString_FAST$(b)    ;The extra code around the API function here is important!
	Local hasExtra = False, sz = BankSize(b)
	If sz = 0
		ResizeBank b, 1 : PokeByte b, 0, 0 : hasExtra = True
	ElseIf PeekByte(b, sz - 1)
		ResizeBank(b), sz + 1 : PokeByte b, sz, 0 : hasExtra = True
	EndIf
	Local res$ = API_BankToString_(b, b, 0)    ; 0 should technically be fine here
	If hasExtra Then ResizeBank(b), sz
	Return res
End Function

Function StringToBank_SLOW(s$)
	Local l = Len(s), b = CreateBank(l), c
	For c = 1 To l
		PokeByte b, c - 1, Asc(Mid(s, c, 1))
	Next
	Return b
End Function

Function BankToString_SLOW$(b)
	Local l = BankSize(b) - 1, s$, c
	For c = 0 To l
		s = s + Chr(PeekByte(b, c))
	Next
	Return s
End Function

You need the userlib .decls found in the archive box below, but the trick itself only uses system DLLs, so no extra files to package with your program.

Important note: because of incompatibilities between the way B3D and C handle strings (the userlibs assume C is your language), API_BankToString_ will not work correctly on any banks containing a 0 byte, which is the string terminator for C strings. It also won't work correctly - possibly causing crashes - if your bank is not null-terminated, so I strongly recommend you make use of the wrapper functions instead of using the raw API functions, which will perform the necessary safety-check.

API_StringToBank_ will still work as expected for B3D strings containing Chr(0), however, and this is likely to be the more useful of the two.

; The decls:

; Quickly copy data from string to bank and bank to string using system functions
; Both of these functions are more usefully wrapped, to hide the dirty details

.lib "Kernel32.dll"

API_StringToBank_(Dest*, Src$, Sz%) : "RtlMoveMemory"

.lib "msvcrt.dll"

; Dest and Src should ideally be the same bank (dirty hack)
API_BankToString_$(Dest*, Src*, Sz%) : "memmove"

; The wrappers:
;
;Function StringToBank_FAST(s$)
;	Local b = CreateBank(Len(s))
;	API_StringToBank_ b, s, BankSize(b)
;	Return b
;End Function
;
;Function BankToString_FAST$(b)    ;The extra code around the API function here is important!
;	Local hasExtra = False, sz = BankSize(b)
;	If sz = 0
;		ResizeBank b, 1 : PokeByte b, 0, 0 : hasExtra = True
;	ElseIf PeekByte(b, sz - 1)
;		ResizeBank(b), sz + 1 : PokeByte b, sz, 0 : hasExtra = True
;	EndIf
;	Local res$ = API_BankToString_(b, b, 0)    ; 0 should technically be fine here
;	If hasExtra Then ResizeBank(b), sz
;	Return res
;End Function
;

Comments

2012

couldnt you memcpy or doesnt that work?

Yasha

2012

memcpy works just as well on my machine, but it also provided no noticeable speedup, so I figured it's better to put the one that doesn't rely on Undefined Behaviour in the public archive.

It's actually just using memmove/memcpy as an identity function because it happens to also return the dest buffer - in fact ~~you could probably~~ I just changed it to pass a 0 for "bytes to copy" and it would be fastest - the work of actually creating the new string is done entirely by B3D's automated glue code for userlib functions that return strings. That's why it's a dirty, sneaky trick: tell B3D that the returned value is a char *, and it will create a string from whatever the function returns (the untouched contents of the bank).

TBH when you're talking about an order-of-magnitude speedup from the "slow copy", the difference between memmove and memcpy is a seriously minor detail, anyway.

virtlands

2013

"FAST bank to string by Yasha"

This is awesome code. I just tried it and received the following results on my PC:

Fast code timing = 0.411 sec
Slow code timing = 25.500 sec

The difference is that the Fast functions are about 62 times faster than the slow B3D code.

This combines well with Yasha's other topic of using pointers on strings:

String banks/data buffers by Yasha
http://www.blitzbasic.com/codearcs/codearcs.php?code=3017#comments

;;-------------------------------------
Function BankToString_FAST$(b)
Return API_BankToString_(b, b, 0) ; 0 should technically be fine here
End Function

In that function, I'm assuming that a B3D string of appropriate length is automatically created. :amazing:

In case those banks have zeroes in them, then we could perhaps temporarily replace the zeroes with a replacement number, not previously occurring.
And then the rough part would be to turn the stand-ins back into zeroes (in the destination string.)

virtlands

2013

Oh my! I just found some performance errors with the Fast functions.

I tested the Fast functions with strings that vary in length from 0 to 1000.

As seen from the screenshots, the BankToString_Fast()
function creates some inaccuracies sometimes:

This first screenshots shows about 7 errors.
[ String lengths are shown from 0 to 32; Errors happen at bank lengths 0,16,17,18,19,20,32. ]

Testing code for string lengths 0 to 64

;; Testing code was created by VirtLands
;; 
;; Algorithms and code taken from: 
;; FAST bank To String by Yasha
;; <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=2972" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2972</a>

 Graphics 800,500,32,2
 ClsColor 222,227,231
 Color 22,121,170 : Cls

 Local b[65]    ;; create this array to store banks
 Local s$
 Local Title$ = "Yasha's Quick Bank Transactions "

 Print Title:Print 

 For z=0 To 65
        b[z] = stringtoBank_Fast( String$("@",z) )                                   ; do a bank deposit
        s$ = banktostring_Fast( b[z] )                                                     ; take cash out...
        Print"bank len ="+BankSize(b[z])+" : Str Len="+Len(s)+" : "+s       ; see the accountant          

        If z=32  ;; pause the screen at this point
                  WaitKey(): Cls :Locate 1,1
                  Print Title:Print 
        End If 
 Next

 For z=0 To 65
           FreeBank b[z]
 Next 

 WaitKey():End   

Function StringToBank_FAST(s$)
	Local b = CreateBank(Len(s))
	API_StringToBank_ b, s, BankSize(b)
	Return b
End Function

Function BankToString_FAST$(b)
	Return API_BankToString_(b, b, 0)    ; 0 should technically be fine here
End Function

Function StringToBank_SLOW(s$)
	Local l = Len(s), b = CreateBank(l), c
	For c = 1 To l
		PokeByte b, c - 1, Asc(Mid(s, c, 1))
	Next
	Return b
End Function

Function BankToString_SLOW$(b)
	Local l = BankSize(b) - 1, s$, c
	For c = 0 To l
		s = s + Chr(PeekByte(b, c))
	Next
	Return s
End Function

Here's a more streamlined program for testing string lengths 0 to 1000.

;; This testing code was created by VirtLands
;; 
;; Algorithms and code taken from: 
;; FAST bank To String by Yasha
;; <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=2972" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2972</a>

 Graphics 660,500,32,2
 ClsColor 222,227,231
 Color 22,121,170 : Cls

 Local Title$ =  " Yasha's Quick Bank Transactions "
 Local b            ;; the bank
 Local s$
 Local e$          ;; the error list
 Local TestStr$  ;;

 Print Title: Print 
 Print" Errors occur on the following [bank] sizes, using  BankToString_Fast(b): ":Print

 For z=0 To 1000                                  ;; try strings of increasing sizes...
          teststr = String$("@",z)
          B =stringtoBank_Fast( teststr )
          S =banktostring_Fast( B )           ;; back to string again...
          If Len(teststr)<>Len(S) 
                    e = e + " "+Len(teststr)
                    If Len(e)>70
                               Print e
                               e = ""
                    End If
          End If 
          FreeBank B 
 Next 
 If Len(e) Then Print e

 WaitKey():End 

Function StringToBank_FAST(s$)
  Local b = CreateBank(Len(s))
  API_StringToBank_ b, s, BankSize(b)
  Return b
End Function

Function BankToString_FAST$(b)
  Return API_BankToString_(b, b, 0)    ; 0 should technically be fine here
End Function

Function StringToBank_SLOW(s$)
   Local l = Len(s), b = CreateBank(l), c
   For c = 1 To l
        PokeByte b, c - 1, Asc(Mid(s, c, 1))
   Next
   Return b
End Function

Function BankToString_SLOW$(b)
   Local l = BankSize(b) - 1, s$, c
   For c = 0 To l
 	s = s + Chr(PeekByte(b, c))
   Next
   Return s
End Function

The errors happen kind of randomly ..

Yasha

2013

Well that's interesting. Bears investigation. Let me get back to ya on that...

EDIT: well, I have an answer for you.

The problem is with API_BankToString_.

Banks are not null-terminated, the data just goes right up to the end. However, B3D's .decls interface glue code (which is the part providing all the work here) expects to be given a null-terminated string - this is why it will return a shorter-than-expected string when the bank contains a 0 byte.

The converse is also in effect: if the end of the bank isn't a 0 byte, the glue code will keep copying string data until it finds one, whether that's still within the bounds of the bank or not! That's why the errors consist of extra data beyond the expected string, but everything put into it originally is still returned.

The obvious fix - to simply trim the result string down to the expected length - is not safe, because if there are no 0 bytes in between the end of the string and unallocated memory, the program will crash. The safe thing is to test the end of the bank to see if it's a 0, and if not, append one (then remove it afterwards because it wasn't part of the user's original data).

This is a C-programming rookie mistake and I'm embarrassed to have left it in there (in my defence, that's because BankToString already has the showstopper bug that it can't copy all strings anyway, so I didn't think anyone would use it).

I will make the necessary change to the example code and add a note explaining that users should copy that whole function.

virtlands

2013

Good luck on that.

Local teststr$, S$, B,L

L = Len(teststr)
B = stringtoBank_Fast( teststr )
S = banktoString_Fast(B)
S = Left$( S, L ) ;; <----

Simply forcing the resultant string S to be of
identical size as the original teststr may be a temporary way of doing it.

Yasha

2013

It is done.

(As I said in comment #5, using Left$ will get the right string data out, but it won't prevent the possibility of a crash.)

Code Archives Forum