Announcement

Collapse
No announcement yet.

Need better (faster) INSTR

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

  • Need better (faster) INSTR

    OK, I've been chasing a bottleneck in my app, and it turns out to be INSTR. Not what I was expecting.

    I have a pool of STRING buffers and use a simple long string of "1' and '0' to control which are allocated / free.

    So when I want a free buffer, I do an INSTR(alloc-string, "1") to get the index of an available buffer.

    Now I'm experiencing very long slowdowns when processing large amounts of data. e.g. when the # of buffers, and the companion allocation-string are in the 500,000 to 1,500,000 entries.

    The slowdown is in the INSTR(alloc-string, "1"). I tried replacing it with a BYTE pointer loop, it actually was worse.

    The alloc-string is not constantly being re-allocated. When a buffer is allocated, the "1" is made a "0" with a simple MID$ change.

    Is there any alternative out there? I'd always hung my hat on INSTR being very efficient.

    Or is there another way to control random allocation of a bunch of string buffers in a simple XXX(1 to gaziliion) as STRING array?

    Any thoughts appreciated

    George

  • #2
    There is a faster version of INSTR posted on the forum somewhere but that's not a good approach.

    Try dimming an array of LONGs, big enough to hold all your buffer numbers.
    Fill the array with those numbers, maybe 1 to 1,000,000. Initially, they'll be in sequence but as bufferes are allocated and deallocated they'll get out of sequence but that doesn't matter.

    Then use 2 pointers to treat the array as a circular list.
    When you need a new buffer, one of the pointers looks it up in the array then increment the pointer.
    When the buffer is no longer needed, put it back into the array at the location pointed to by the second pointer then increment that pointer.

    When a pointer reaches the limit of the array, reset it to 1 to make it a circular list.
    If the 2 pointers catch each other then you've run out of buffers.

    This way, a free buffer number is always immediately available without a search.

    Comment


    • #3
      Faster INSTR:
      https://forum.powerbasic.com/forum/u...785#post790785

      Comment


      • #4
        George,

        I have not got the entire logic of what you are doing but repeatedly scanning very long strings is always going to be a problem, no matter how fast the INSTR version you use is. At its simplest just producing a branching layout "IF ELSEIF ELSE END IF" to construct a rudimentary tree separated at an alphabetical level would dramatically reduce the string lengths you have to scan. It would be far faster to climb an IF type tree that linear scanning massive length strings.
        hutch at movsd dot com
        The MASM Forum

        www.masm32.com

        Comment


        • #5
          It sounds like you are using a ASCII char bitmap to manage buffer allocations (similar to a FAT bitmap). You can continue to use that but why not use a list of pointers in 2 arrays. One array keeps free buffer pointers (1..n) and the other keeps the used buffer pointers (1..x). When a buffer is used you reduce n by 1 (n=n-1). In turn pointer is added to the end of the used pointer array (x=x+1). Now, when a buffer is freed (w), you incr n+1 and move that pointer back there and shift the used pointers down 1 wherever it was freed from (w..x moves to w-1..x-1 and x=x-1) which should be a fairly quick process,( i.e. array delete).

          The other alternative is rather than ASCII string to store ASCII 0/1s, use an array of bytes or longs to store 0/1 which should be lightning quick because there isn't all the string handling overhead to do the same thing.
          Last edited by George Bleck; 7 Jun 2020, 11:54 PM.
          <b>George W. Bleck</b>
          <img src='http://www.blecktech.com/myemail.gif'>

          Comment


          • #6
            Maybe a simple LIFO stack would work. Begin by pushing the numbers of all the available buffers onto the stack then pop for the number of a free buffer and push the number of a buffer to release it.

            Comment


            • #7
              First thing I note is that you are using 8 bits to store a single on/off flag. You can do that with 1 bit.

              One possibility:
              If you need 1.5 million flags, create a string of NUL$(185,000) which is 1.5 million bits
              Loop through the string 64 bits at a time using a QUAD PTR or PEEK(QUAD.addr) , which means a maximum of 23,437 steps
              Test each value for = &HFFFFFFFFFFFFFFFF (i.e. no zero bits)
              Once your test fails, you have an empty slot in your current set of 64 buffers,
              Find the first 0 bit in the value and calculate the corresponding buffer number (loop count * 64 + offset into quad)
              INSTR(BIN$(qTemp,64)) would be one way
              Set the bit in the value and POKE it back into the string where you read it from.
              (Or you could use PEEK instead of a pointer)

              To release a buffer, calculate a byte offset (BufferNo / 8), PEEK that location, AND the byte with BufferNo MOD 8 and POKE the new value
              (Off the top of my head quickly, so some of the above may contain off-by-one errors!)

              Comment


              • #8
                I am cconfused . As long as your not copying the buffers or changing their length with an assignment statement that could slow the heck out of it , then maybe you can prequalify the buffers in some way.
                You said your not reallocating,meaning to me to be changing .
                p purvis

                Comment


                • #9
                  > the "1" is made a "0" with a simple MID$ change.

                  That, sounds unefficient to me. Why not use fixed length strings and simply clear them with sBuf1 = ""? And/or store string pointers to cleared/free string buffers in an array so you don't have to look for them - just grab from array? Could be I don't understand what you do - I'm sure if you can wrap up a small example showing what you do, there are several here who can help you find a better and faster solution to this task.

                  Comment


                  • #10
                    Using Bits and checking a Quad at a time as per Post #7 is at least 20 times as fast as INSTR and "0"/"1" on a 1.5 million flag string

                    ---------------------------
                    PowerBASIC
                    ---------------------------
                    130768 tix for bits
                    3155740 tix for '0' and '1'
                    ---------------------------
                    OK
                    ---------------------------

                    Once again we see preconceptions resulting in the wrong question being asked. It's not about a faster INSTR or "a way to control random allocation of a bunch of string buffers in a simple XXX(1 to gaziliion) as STRING array"

                    The question should have been "How to manage a gazillion flags efficiently"

                    '
                    Code:
                    #COMPILE EXE
                    #DIM ALL
                    
                    #INCLUDE ONCE "WIN32API.INC"
                    
                    FUNCTION PBMAIN () AS LONG
                      LOCAL sBuffers AS STRING
                      LOCAL sBuffers2 AS STRING
                      LOCAL pBuf AS QUAD PTR
                      LOCAL lptr,BufferNo,x AS LONG
                      LOCAL q,q2 AS QUAD
                    
                      'Uncomment to test times for extreme case
                      GOTO TestLong
                    
                       sBuffers = NUL$(187500)  '1,500,000 bit flags
                       pBuf = STRPTR(sBuffers)
                       DIM buf(1 TO 187500) AS BYTE AT pBuf
                       'Testing, set first 50 buffers as used
                       FOR x = 1 TO 50
                           BufferNo = x
                           GOSUB SetBuffer
                       NEXT
                    
                      GOSUB getbuffer
                      ? "First Available Buffer = " & STR$(bufferNo)
                    
                      BufferNo = 23
                      GOSUB clearbuffer
                      GOSUB getbuffer
                      ? "First Available Buffer = " & STR$(bufferNo)
                    
                    EXIT FUNCTION
                    '====== TEST ROUTINE ==============
                    TestLong:
                      'Test buffers, mainly 1's
                      sBuffers =  STRING$(187500,CHR$(255))
                      pBuf = STRPTR(sBuffers)
                      DIM buf(1 TO 187500) AS BYTE AT pBuf
                      BufferNo = 1499997
                      GOSUB ClearBuffer
                      TIX q
                      GOSUB GetBuffer
                      TIX END q
                      ? "Bits, Buffer no: " & STR$(BufferNo)
                    
                      BufferNo = 0
                      sBuffers2 = STRING$(1499996,"1") & "0111"
                      TIX q2
                      GOSUB GetBuffer2
                      TIX END q2
                      ? "'0'/'1' Buffer no: " & STR$(BufferNo)
                    
                      ?  STR$(q) & " tix for bits"& $CRLF &  STR$(q2) & " tix for '0' and '1'"
                    
                     EXIT FUNCTION
                    ' For coparative test
                    GetBuffer2:
                       BufferNo = INSTR(sBuffers2,"0")
                       RETURN
                    
                    
                    '=========== BUFFER SUBS =================
                    GetBuffer:
                       FOR lPtr = 0 TO 23437
                         IF @pBUF[lPtr] <> &HFFFFFFFFFFFFFFFF THEN
                             BufferNo = lPtr * 64 + 65- INSTR(-1,BIN$(@pBUF[lptr],64),"0")
                             RETURN
                         END IF
                       NEXT
                       RETURN
                    
                    SetBuffer:
                       BIT SET buf(1),BufferNo-1
                       RETURN
                    
                    ClearBuffer:
                       BIT RESET buf(1),BufferNo-1
                       RETURN
                    END FUNCTION
                    '

                    Comment


                    • #11
                      Or is there another way to control random allocation of a bunch of string buffers in a simple XXX(1 to gaziliion) as STRING array?
                      Maybe don't preallocate and locate one which is available; instead allocate and deallocate as needed.

                      Here's a starter:

                      ** DYNAMIC ALLOCATION AND LINKED LISTS
                      My December 1998 article "Make Haste, Not Waste" in BASICally Speaking
                      magazine (no longer published) describes EXACTLY this; not only that, it
                      keeps the linked list of UDTs sorted by three separate keys at one time. In
                      April 1999 the PB/CC (Windows) version of this software was published.
                      The corrected PUBLIC DOMAIN code for the PB/DOS version of the code was published at
                      the same time. Both Windows and DOS code may be downloaded from:
                      Dynamic Allocation and Linked Lists for PB/CC and PB/DOS


                      I checked the URL this AM and it's still good, but that's an IMS web site. Alan and I had a nice exchange of email last well, but I think I should probably get that file posted here on the PB site.

                      Note the files posted on the IMS web site are CODE ONLY and the documentation is in the articles themselves, which as far as I know are not available. Maybe I'll ask Alan to make them available.

                      Heck as long as this stuff still works (above includes code for both MS-DOC and for Win/32), why not?:

                      Note: PB now includes intrinsic BASIC language support for both allocation/deallocation and linked lists. At least this will show you how it can be used.

                      (Or, as I suggested to someone else recently, I could do it for you if you are interested in supplementing my Social Security check. )

                      MCM


                      Michael Mattias
                      Tal Systems Inc. (retired)
                      Racine WI USA
                      [email protected]
                      http://www.talsystems.com

                      Comment


                      • #12
                        Wow! SO much interest. I thank you all. I know the method I've been using isn't the greatest, but it has served very well in my app (an Editor) for more than a dozen years and has not been a problem. But lately I have some users who are editing files with 1 or 2 million lines, and this has obviously demonstrated the poor design. There are some other areas in the App also showing the strain and I'm addressing those as well. I believe switching to a bit flag array is the best solution for me.

                        Stuart: Many thanks for the sample code. Question: If the pool needs expanding, are the addition flag bytes just appended to the sBuffer string? I believe so as I read it.

                        Again, thanks to you all.

                        George

                        MCM: You post came in while I was answering. Changing the App's whole storage technique to a Linked-List style is, right now, just too big a change. There's 50K+ lines of code, I won't live long enough to tackle a change like that. But many thanks for the link.

                        Comment


                        • #13
                          George. Maybe it is not your code that is of the needing of a change if there are that huge number of lines in a single file being edited.
                          p purvis

                          Comment


                          • #14
                            If you run out of buffers and need to extend the string, you need to refresh the Varptr and redim the Buf() array since the location in memory of sBuffers will change.
                            Same if you decide to reduce the number of buffers for any reason.

                            '
                            Code:
                            x = 50' Number of  buffers to add/delete, will be rounded  to multiple of 64
                            GOSUB AddBuffers
                            ...
                            
                            AddBuffers:
                            'Add or remove x buffers based on sign of x
                            'x is rounded away from 0 to a multiple of 64 bits
                            'Caution, that means that if x = -1,  8 bytes/64 buffers will be removed!
                               SELECT CASE x
                                   CASE > 0
                                      x +=  63 - (x-1) MOD 64
                                      sBuffers += STRING$(x/8, CHR$(0))
                                   CASE < 0
                                      x -= 63 - ABS(x+1) MOD 64
                                      sBuffers = LEFT$(sBuffers,x/8)
                                   CASE ELSE '0
                                      RETURN
                               END SELECT
                               pBuf = STRPTR(sBuffers)
                               REDIM buf(1 TO LEN(sBuffers)) AT pBuf
                               RETURN
                            '

                            Comment


                            • #15
                              MCM: You post came in while I was answering. Changing the App's whole storage technique to a Linked-List style is, right now, just too big a change. There's 50K+ lines of code, I won't live long enough to tackle a change like that. But many thanks for the link.
                              Ok, let's try a smaller change. (This occurred to me after my first post)

                              Instead of searching a long list looking for what's currently available, while not changing your overall storage design, why not add a SEPARATE list of "available," adding or deleting from that list dynamically?

                              My point being (in either case), when an operation is slow, update your design to avoid that operation.

                              MCM
                              Michael Mattias
                              Tal Systems Inc. (retired)
                              Racine WI USA
                              [email protected]
                              http://www.talsystems.com

                              Comment


                              • #16
                                I've updated the code in Post # 10 to include initialiising number of buffers, changing number of buffers and separated out the test routines from the meat of the buffer management to make it easier to follow. (Also debugged a couple of edge cases )

                                See next post for link to final version in Source Code forum
                                Last edited by Stuart McLachlan; 9 Jun 2020, 02:34 AM.

                                Comment


                                • #17
                                  I changed "Buffers" to "Flags" to make it more general purpose and easier to locate in the future and posted in Source Code.
                                  https://forum.powerbasic.com/forum/u...ags#post795140

                                  Comment


                                  • #18
                                    Wait a minute ... MCM is back?

                                    Didn't realized that earlier. Welcome back, Michael!

                                    Comment


                                    • #19
                                      Stuart: Thanks for the extra effort, very useful.

                                      George

                                      Comment


                                      • #20
                                        I've just added a new version of the "flag manager" in the source code forum:

                                        https://forum.powerbasic.com/forum/u...174#post795174

                                        This version uses a global flag buffer and FASTPROCs to make it "plug and play" into another applications:
                                        Added FlagIsSet test (how did I miss that one first time round? )

                                        N.B. Requires PBWin10/PBCC6

                                        Comment

                                        Working...
                                        X