Announcement

Collapse
No announcement yet.

STRING CONCATENATION - What really is the fastest most efficient way?

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • STRING CONCATENATION - What really is the fastest most efficient way?

    I have all sorts of ACCUMULATING_STRING = ACCUMULATING_STRING + RECEIVED_DATA_STRING code.

    I keep reading this is very slow and wasteful. What is the fastest most efficient way to do this?

    Here is what I think I am hearing:

    1) Allocate the ACCUMULATING_STRING once in the beginning. Not doing that over and over.

    2) Then what? Use POKE to put the new data in the string?



  • #2
    Have a look at PB's StringBuilder object. From the manual:

    The StringBuilder object offers the ability to concatenate many string sections at a very high level of performance. The speed of execution is particularly noticeable when the concatenation is performed in many separate operations over a period of time. If all of the string sections are known and available at once, the use of the BUILD$() function could be a better choice. However, both options offer a very large boost as compared to the standard concatenation operators (& or +). In addition to concatenation, the StringBuilder Class also offers a few additional string operations to assist in building the string.
    I also seem to remember a comparison thread about string concatenation where it indeed did perform quite well.

    Comment


    • #3
      Not sure it works for you but you could store all the adds in an array then JOIN it later.
      <b>George W. Bleck</b>
      <img src='http://www.blecktech.com/myemail.gif'>

      Comment


      • #4
        David,

        This code, that I gave you last week, will be hard to beat.
        It handles maximum buffer possible and decreases buffer with each receive, buffer over-run isn't possible and doesn't need join$.
        If you need an array and a string then use an array and join (like George has said.)
        There is no concatenation used with MID$ to another string.
        Is peek/poke or stringbuilder faster? I doubt any difference if trying to save a second.

        If on a local network and 100,000 bytes were sent it is possible to receive it in a single packet because of the decreasing buffer size.
        Code:
        FUNCTION PBMAIN () AS LONG
        
         LOCAL sPacket, sBuffer AS STRING
         LOCAL StartByte, BytesToReceive, BytesLeft AS LONG
        
         BytestoReceive = 9999999  'David, Do you know or can you pass the number of bytes to receive?
        
         BytesLeft = BytesToReceive
         sPacket = SPACE$(BytesToReceive) 'allocate space once
         StartByte = 1
        
         DO
          TCP RECV tcpfilenumber,BytesLeft, sBuffer
          IF ERR OR LEN(sBuffer) = 0 THEN EXIT DO
          MID$(sPacket,StartByte) = sBuffer
          StartByte = StartByte + LEN(sBuffer)
          BytesLeft = BytesLeft-LEN(sBuffer)
         LOOP UNTIL BytesLeft < 1
        
        END FUNCTION
        Last edited by Mike Doty; 12 Aug 2019, 05:54 PM.
        https://duckduckgo.com instead of google

        Comment


        • #5
          David,
          Or simply use BUILD$. The more "+" and "&" you replace by using it the faster it gets compared to the typical concatenation method of + or &.

          This
          lsA = BUILD$(lsA, gsX, gsY, gsZ, $CRLF)

          is >= 3 and <= 5 times faster than this.
          lsA = lsA + gsX + gsY + gsZ + $CRLF

          If you are just replacing 1 item ("+" or "&") each time through as in your FIFO buffer example then you may not notice much difference between the 2 methods.

          BUILD$ shines when you are concatenating multiple items at one time.

          NOTE:
          I have not done a benchmark comparison between (StringBuilder or JOIN$) and BUILD$.

          Help says,
          "The StringBuilder object offers the ability to concatenate many string sections at a very high level of performance. The speed of execution is particularly noticeable when the concatenation is performed in many separate operations over a period of time. If all of the string sections are known and available at once, the use of the BUILD$() function could be a better choice. However, both options offer a very large boost as compared to the standard concatenation operators (& or +). In addition to concatenation, the StringBuilder Class also offers a few additional string operations to assist in building the string."

          I just benchmark compared this:
          IsA = IsA + gsX

          with this
          IsA = BUILD$(IsA, gsX)

          Result: No significant difference in the methods when tested at 10,000 iterations.

          Just guessing here...
          Surely JOIN$ is using StringBuilder or BUILD$ in the background to concatenate the strings stored in the array. You still have the overhead of putting the strings in the array and maintaining the array(adding a cell, clearing all cells, whatever).

          From my perspective it looks like your current method should be fine.

          Comment


          • #6
            I doubt the actual string building will be the bottleneck there - it's probably the RECEIVED_DATA_STRING - which I assume comes in from TCP RECV loop - that adds most time. Not much to do about that.

            Comment


            • #7
              Originally posted by David Clarke View Post
              I have all sorts of ACCUMULATING_STRING = ACCUMULATING_STRING + RECEIVED_DATA_STRING code.

              I keep reading this is very slow and wasteful. What is the fastest most efficient way to do this?

              Here is what I think I am hearing:

              1) Allocate the ACCUMULATING_STRING once in the beginning. Not doing that over and over.

              2) Then what? Use POKE to put the new data in the string?
              At a guess, you pass a buffer address to the function which provides the new string. If you pre-allocate memory sufficient to hold the concatenated strings, and keep track of the first free byte or word of it, you can have the function do the concatenation for you.

              Comment


              • #8
                This may be of use:

                https://forum.powerbasic.com/forum/u...-string-append

                Comment


                • #9
                  Originally posted by Chris Holbrook View Post
                  At a guess, you pass a buffer address to the function which provides the new string. If you pre-allocate memory sufficient to hold the concatenated strings, and keep track of the first free byte or word of it, you can have the function do the concatenation for you.
                  Something like this? TCP is not my home turf so I'll pretend there is a function getsomedata which returns a byte count. There is no need to concatenate strings or even learn Assembly Language.

                  Code:
                      local pb as byte ptr
                      local buffer as string
                      local datalength as long
                  
                      buffer = nul$(%mybufferlength)
                      pb = strptr(buffer)
                      do
                          datalength = getsomedata( #99, %mychunksize, pSbuffer)
                          psbuffer += %mychunksize
                          if datalength < %mychunksize then exit loop ' done
                          if psbuffer - strptr(buffer) > %mybufferlength then
                              ? "overflow!"
                              exit function
                          end if
                      loop
                      ' string of datalength bytes is now complete in buffer
                  That's not tested code, of course, just a sketch!

                  Comment


                  • #10
                    If you have an aversion to ASM, then Stringbuilder with a sufficently large initial size will be very hard to beat.

                    Code:
                    #COMPILE EXE
                    #DIM ALL
                    
                    %MaxreceiveBytes = 50000000 ' '50MB :-)
                    
                    FUNCTION PBMAIN () AS LONG
                      LOCAL sb AS ISTRINGBUILDERA
                      LOCAL ACCUMULATING_STRING,  RECEIVED_DATA_STRING AS STRING
                      sb = CLASS "StringBuilderA"
                      sb.capacity = %MaxReceiveBytes
                    ' ...
                      DO
                         ' TCP code
                         '  ...
                         sb.add RECEIVED_DATA_STRING
                         ' More TCP code
                         ' ...
                      LOOP
                      ACCUMULATING_STRING = sb.string
                    ' ...
                    END FUNCTION

                    Comment


                    • #11
                      Originally posted by Stuart McLachlan View Post
                      If you have an aversion to ASM, then Stringbuilder with a sufficently large initial size will be very hard to beat.
                      I don't have such an aversion, but why use any concatenation technique when you can avoid it?

                      Comment


                      • #12
                        Originally posted by Chris Holbrook View Post
                        I don't have such an aversion, but why use any concatenation technique when you can avoid it?
                        Steve's ASM routine I linked to doesn't use any concatenation technique. It's essentially his ASM implementatin of StringBuilder or any of the other previously discussed versions of POKE$ing or MID$ing into a location within a predefined large string of $Nuls or spaces..

                        Comment


                        • #13
                          The szappend algo that Stuart linked to is basically a stream append that you sequentially pass data to that writes to a pre-allocated buffer. If you use the version that passes the address of the data to append in the EAX register you save on the overhead of repeatedly calling the same procedure. Now while I am certainly not an expert in TCP/IP processing, if you can stream the data input written to a buffer address without converting back and forth from basic string you can keep the overhead down which will reduce at least one task in reading data of this type.

                          The algo uses a current location counter that you usually set to zero (0) at the start and keep feeding the return value which is the updated current location counter to the variable. Now while this algo was designed for very high speed data sourcing of equally very large data (IE: An array or similar), even with a gigabit network connection, you are not going to come near the speed of data being read or sourced from memory in a computer.

                          A basic string version can be done but you pay the price of multiple conversions.
                          hutch at movsd dot com
                          The MASM Forum

                          www.masm32.com

                          Comment


                          • #14
                            All,
                            Just down road, I presume David will be using a locking mechanism so that reads on the FIFO buffer are prevented while the buffer is being modified by whatever method he uses to build the buffer. If he has not entertained that then I am merely suggesting it here. It was part of the code that I provided to him on a differentr post. Nothing fancy really.

                            David,
                            How many receives are you planning on getting before you start processing the data? 10, 20, 100, unknown? How are you going to read the data and what method are you going to use to apply the data? Shouldn't those questions be answered before you finalize your collection method? I'd bet you'd want to keep it simple and easy to maintain.

                            Comment


                            • #15
                              Dual writers?
                              Also, BUILD$ is not intended within a loop to concatenate a single variable.
                              If he is using ASYNC he should have mentioned that.
                              TCP RECV is a blocking statement (which you must know.)
                              Never found out if he knows the number of incoming bytes which is extremely useful.
                              https://duckduckgo.com instead of google

                              Comment


                              • #16
                                Thanks Mike,
                                That's ok. I guess we are all in limbo again. Ha Ha
                                David is probably creating another post question in capitol letters while we are all here.

                                Oh Mike, I was referring to the reads on his FIFO buffer.
                                See you

                                Comment


                                • #17
                                  "David, Do you know or can you pass the number of bytes to receive?"

                                  I do know that although in practical results if you quickly respond to the "data is waiting" event message (%FD_READ) you will drain the buffer before many bytes can accumulate. I have never seen more that about 30k in one read, not sure if there is an upper limit (time to test that!). All this speed stuff is because I have a LOT of connections at any moment, around 220 sending and receiving at the same time. So I am looking for any incremental improvements. At the same time I am playing with overlapped TCP as I have read that it will have a dramatic positive effect on simultaneous comm. Since I already treat my TCP as asynch I am not sure how overlapped is better. I believe what they are talking about is the difference between having 1 thread per connection vs overlapped on 1 thread. 1 thread is way faster. And, my first swat at this a few years back spawned a thread for each TCP ACCEPT. Now I have all TCP on one dialog in a separate thread.

                                  I do know everything about the data as I make it myself in another program. Each "package" has a header with the byte count and sometimes MD5 for the following data. So we concatenate and count the received bytes then MD5 check it if it is super critical. Sometimes we have an end of file marker. And of course there is TCP LINE INPUT for when you know the data will not contain any $CRLF as part of the data.


                                  Last few days I have been trying to do file transfers as fast as FileZilla so I have been tuning, adjusting and testing changes for speed impact.

                                  Lots of good ideas in these posts!!

                                  I am going to go play with Stringbuilder and The szappend algo that Stuart linked to.

                                  Comment


                                  • #18
                                    Wow! That is a bunch of messages. So I'm thinking you are creating a FIFO buffer for each device you communicate with based on their ID. Right? Or are you handling them all in 1 buffer and separating them out later?

                                    Very Strange. I have never ran into a situation where the data was not there after an %FD_READ command was issued. If your messages are coming in from multiple devices as you say then I can see that the %FD_READ may get out of sync with the data streams. Do your clients hold their data when they detect the server is busy and then send only when the server is available? Hopefully your clients are behaving and not conflicting with each other's messages. That would be a nightmare to weed out overlapping and conflicting messages.

                                    Possible self-inflicted denial of service attack.

                                    Likely this would be an improvement in accuracy albeit a slower method:

                                    Server
                                    ID 01 send me your data.

                                    Client
                                    Sends its data

                                    Server
                                    ID 02 send me your data.

                                    Client
                                    Sends its data

                                    .
                                    .
                                    .

                                    Server
                                    ID 50 send me your data.

                                    Client
                                    Sends its data

                                    Should not be any conflicts with this synchronized method.
                                    Last edited by Jim Fritts; 13 Aug 2019, 08:26 AM.

                                    Comment


                                    • #19
                                      Originally posted by David Clarke View Post

                                      At the same time I am playing with overlapped TCP as I have read that it will have a dramatic positive effect on simultaneous comm. Since I already treat my TCP as asynch I am not sure how overlapped is better. I believe what they are talking about is the difference between having 1 thread per connection vs overlapped on 1 thread. 1 thread is way faster. And, my first swat at this a few years back spawned a thread for each TCP ACCEPT. Now I have all TCP on one dialog in a separate thread.
                                      I believe that the advantage of overlapped IO is not needing to copy data between buffers. If you pass your own buffer to Winsock using overlapped IO, Winsock will work with your buffer and save time with a copy from a Winsock buffer to yours - and maybe some internal memory allocation/de-allocation. This should be noticeable at really high packet rates. If you have multiple threads service the same socket, you can, perhaps, see some further improvements. But, there may not be a guarantee of the sequence of data. Some assembly (not ASM) may be required.

                                      I also suspect that creating a buffer large enough to hold the entire message, or the largest message that you expect to receive, and then moving data into that buffer (e.g. MID$, POKE$, MEMORY COPY) will always be faster than concatenating strings - and all of the attendant memory allocation that goes on under the covers.

                                      Comment


                                      • #20
                                        Interesting point Jerry! I am going to read more about that.


                                        Hi Jim here are some answers:

                                        I have two arrays TCP_RECV(999) AND ACCUMULATED_TCP_RECV (999)
                                        Each communicating device (socket) has its own receive buffers (those two arrays) indexed by a thing I call CONTROLLER_UNIQUE_ID that is looked up by MAC Address in a database. That is how we keep everything separate. So far never lost any data in 4 years and hundreds of million communications.

                                        I am trying to figure out if there is a practical upper limit to the number of connections I can service on one computer. Something of an ongoing project. I could make it so I only call CONVERT_FILE_HANDLE_TO_FILE_NUMBER once in the first connection- then keep that info in an array....

                                        I have to build a simulator thing to test my TCP RECV thing. I will let everyone know what I find out.


                                        This is the TCP RECV callback handler:

                                        Code:
                                        SELECT CASE CB.LPARAM
                                        
                                                    CASE %FD_READ    ' 1
                                                      'TEXT_TO_SCREEN_1 "%FD_READ"
                                                      TCP_RECV(CONVERT_FILE_HANDLE_TO_FILE_NUMBER(CB.WPARAM))
                                        Here is CONVERT_FILE_HANDLE_TO_FILE_NUMBER:
                                        Code:
                                         FUNCTION CONVERT_FILE_HANDLE_TO_FILE_NUMBER(FILE_HANDLE AS DWORD) AS LONG
                                        
                                           LOCAL Looper     AS LONG
                                           LOCAL hFileOsTry AS LONG
                                           LOCAL FileNumTry AS LONG
                                        
                                           Looper = 1                                'FILEATTR(Looper, 3) is one based
                                           DO
                                           FileNumTry = FILEATTR(Looper, 3)          '3 enumerates existing file numbers.
                                           IF FileNumTry = -1 THEN                   'No more handles to scan
                                             EXIT LOOP                               'FUNCTION will return zero, so nothing found, could also be setted to -1 if needed
                                           ELSE
                                             IF FILEATTR(FileNumTry, 0) THEN         '0 for "open state", return TRUE if file is open
                                               hFileOsTry = FILEATTR(FileNumTry, 2)  'Get the coresponding operating system file handle
                                               IF hFileOsTry = FILE_HANDLE THEN
                                                 FUNCTION = FileNumTry
                                               END IF
                                             END IF
                                           END IF
                                           INCR Looper
                                           LOOP
                                        
                                         END FUNCTION


                                        Comment

                                        Working...
                                        X