Announcement

Collapse
No announcement yet.

inverting an array

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

  • #21
    Originally posted by Michael Mattias View Post
    Nothing quite like hitting the array engine twice per loop with a fresh inline subtraction each time when pointer variables would let you use a couple of INCR/DECR instructions instead.
    It's quite efficient tho. I didn't see an improvement w/ pointers.

    Comment


    • #22
      >I didn't see an improvement w/ pointers.

      Show code.
      Michael Mattias
      Tal Systems (retired)
      Port Washington WI USA
      [email protected]
      http://www.talsystems.com

      Comment


      • #23
        Meanwhile the guy that started this thread, that solved his problem in more than one way, has moved on to other bigger and better issues. Here we are trying to get things backward quicker.:hmmm:
        Rod
        In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

        Comment


        • #24
          >show code
          Code:
              aPtr1 = VARPTR(a(0))
              aPtr2 = VARPTR(a(2000000))
              FOR ii = 0 TO %ARRAYSIZE / 2
                 SWAP @aPtr1, @aPtr2
                 INCR aPtr1
                 DECR aPtr2
              NEXT
          >Meanwhile the guy that started this thread...
          Yes, it may be academic, but I for one was surprised at the big 124x speed difference so thought I'd mention it. That's a large percentage move.
          Last edited by John Gleason; 30 Aug 2008, 09:27 AM.

          Comment


          • #25
            John,
            I for one was surprised at the big 124x speed difference
            Really? It doesn't surprise me at all!
            For each item of data a straight swap is very much simpler than a sort and a swap algorithm of N items has a complexity or order N but a sort algorithm is anything from N*Log(N) to N^2 so as the array gets bigger the sort becomes increasingly bad compared to a swap.

            Paul.

            Comment


            • #26
              Imo swap already swap's pointers..?
              Not data..
              So is there a need to use pointers?
              hellobasic

              Comment


              • #27
                >Imo swap already swap's pointers..?
                Yep, I agree and didn't see a difference. MCM had asked about it so I posted the code.

                >N^2
                For some reason, even tho I know about it, exponential increases still seem to baffle my linear brain.

                Comment


                • #28
                  I don't normally get involved in these peeing contests, but your code was good and it SHOULD have been faster.

                  But I recalled something I read here in the mists of times long past about the SWAP instruction being not quite the fastest tool in the box.

                  So.... I decided to eschew the use of SWAP and handle it myself with a temporary variable.

                  I put all four methods into the demo and got these results:
                  Code:
                  Creating test array of 20,000,001 elements
                  
                  Now using ARRAY SORT (DESCEND)..
                  ARRAY SORT (DESCEND) took 75.0465
                  
                  Now using SWAP of Array Elements (uses array engine)  ...
                  SWAP thru array engine took .374625000000002
                  
                  Now using PTR with SWAP (no array engine)
                  PTR with SWAP (no array engine) took .390625
                  
                  Now using PTR (no array engine no SWAP ) with temp var
                  Using PTR (no array engine no SWAP ) with temp var took 6.20000000000012E-2
                  
                  Freeing 'A()'
                  A() freed, end of demonstration
                  Rather than 120 times difference, I got pretty much a wash on "PTR using array engine" and "PTR not using array engine".

                  But eschewing SWAP made a pretty nice difference

                  MCM
                  Code:
                  'Testswap.bas
                  ' MCM
                  ' 08-30-08
                  ' PB/CC 4.03
                  
                  #COMPILE  EXE
                  #DIM      ALL
                  #REGISTER NONE           ' we'll decide ourselves, thank you anyway.
                  %ARRAYSIZE = 20000000    '   2,000,000 too fast on my machine, below timer resolution
                                           '  10,000,000 also too fast
                                           '  darned I wish compiler supported comma-formatted numbers here;
                                           '  counting the zeros stinks.
                                         
                  FUNCTION PBMAIN () AS LONG
                      
                    REGISTER ii AS LONG, l AS LONG
                    
                    LOCAL t AS SINGLE
                    LOCAL A() AS STRING
                    LOCAL aPtr1, aPtr2 AS LONG PTR
                    
                    ? USING$ ("Creating test array of #, elements", %ARRAYSIZE + 1)
                    REDIM a(%ARRAYSIZE)
                    FOR ii = 0 TO %ARRAYSIZE
                         a(ii) = MKL$(ii)   'fill a() with test string data
                    NEXT
                    ?
                  
                  '---------------------------------------------------------------
                      ? "Now using ARRAY SORT (DESCEND).."
                      t     = TIMER
                      ARRAY SORT a(), DESCEND
                      ? "ARRAY SORT (DESCEND) took" & STR$(TIMER - t)
                      ?
                  '---------------------------------------------------------------
                      ? "Now using SWAP of Array Elements (uses array engine)  ..."
                      t      = TIMER
                      FOR ii = 0 TO %ARRAYSIZE \ 2     ' I think these need to be integer division
                         SWAP a(%ARRAYSIZE - ii), a(ii) 'invert it in place
                      NEXT
                      ? "SWAP thru array engine took"   & STR$(TIMER - t)
                      ?
                      
                  '---------------------------------------------------------------
                      ? "Now using PTR with SWAP (no array engine)"
                      t     = TIMER
                      aPtr1 = VARPTR(a(0))
                      aPtr2 = VARPTR(a(%ARRAYSIZE))
                      FOR ii = 0 TO %ARRAYSIZE / 2
                         SWAP @aPtr1, @aPtr2
                         INCR aPtr1
                         DECR aPtr2
                      NEXT
                      ? "PTR with SWAP (no array engine) took"   & STR$(TIMER - t)
                      ?
                      
                  '---------------------------------------------------------------
                      ? "Now using PTR (no array engine no SWAP ) with temp var"
                      'WAITKEY$
                      t     = TIMER
                      t     = TIMER
                      aPtr1 = VARPTR(a(0))
                      aPtr2 = VARPTR(a(%ARRAYSIZE))
                  
                      FOR ii = 0 TO %ARRAYSIZE / 2
                         l      =  @aptr2            ' save high value
                         @aPtr2 =  @aPtr1            ' move low value to high value
                         @aPtr1 = l                  ' move former high value to low value
                         INCR     aPtr1
                         DECR     aPtr2
                     NEXT
                      
                      ? "Using PTR (no array engine no SWAP ) with temp var took"   & STR$(TIMER - t)
                      ?
                      
                      ? "Freeing 'A()'"    ' this takes a while at 20,000,000 elements!
                      ERASE A()
                      ? "A() freed, end of demonstration"
                      
                     WAITKEY$
                  
                      
                  END FUNCTION
                  Michael Mattias
                  Tal Systems (retired)
                  Port Washington WI USA
                  [email protected]
                  http://www.talsystems.com

                  Comment


                  • #29
                    Wholly begeebers, that's a screamer and a half!

                    Comment


                    • #30
                      Any newbies looking to speed up their programs need to remember something:

                      The PB intrinsic functions - e.g., SWAP() - are perforce generic, and include all kinds of checking for data types, checking for null pointers, setting ERR and other goodies... the things which make those functions safe and easy to use.

                      All optimization, however, is application-specific. That is, there is no such thing as the "universal silver bullet."

                      eg in above... I treated the PTRs to the array elements not as what they are - "pointers to string handles" - but as pointers to signed LONG integers, and LONG integers are what the compiler eats for breakfast.

                      But I could only do that because in this particular application I know what is being SWAP'ed is in fact a 32-bit entity which is KNOWN to be valid ... and since you can treat any 32-bit entity as a LONG integer, I did so to take advantage of that compiler feature.
                      Michael Mattias
                      Tal Systems (retired)
                      Port Washington WI USA
                      [email protected]
                      http://www.talsystems.com

                      Comment


                      • #31
                        Originally posted by Michael Mattias View Post
                        Any newbies looking to speed up their programs need to remember something:

                        The PB intrinsic functions - e.g., SWAP() - are perforce generic, and include all kinds of checking for data types, checking for null pointers, setting ERR and other goodies... the things which make those functions safe and easy to use.

                        But I could only do that because in this particular application I know what is being SWAP'ed is in fact a 32-bit entity which is KNOWN to be valid ... and since you can treat any 32-bit entity as a LONG integer, I did so to take advantage of that compiler feature.
                        Maybe then SWAP should have an optional type specifier, either SWAP??? a,b or SWAP SINGLE a,b. Leaving it out would be the same kind of SWAP we have now, but using it would cause a compile-time check on the variables.

                        If you want to swap integers, what about using the stack instead of a temp variable?
                        Erich Schulman (KT4VOL/KTN4CA)
                        Go Big Orange

                        Comment


                        • #32
                          Perhaps you could leave the array uninverted* and access the required element with:
                          A$=b$(UBOUND(b$)-requiredelement)
                          May be the quickest.
                          (* a non word in place of the non word verted meaning not inverted)
                          Last edited by Rodney Hicks; 30 Aug 2008, 01:58 PM.
                          Rod
                          In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                          Comment


                          • #33
                            SWAP() has been in BASIC since the hatchet was a hammer so you'd probably want to go slow on any changes or enhancements to it...

                            Besides, any "non-optimal" speed in SWAP is probably not in the data-type resolution code.....ooh, ooh..... wait a minute....

                            I wonder if "swap a, b" works like "select case x".... which ALWAYS (thru 8x anyway) uses the EXT (single? double?) form of numeric variables? In which case, "SWAP&" and "SWAP!" and "SWAP##" might make some sense after all...... or maybe even "SWAP AS LONG x, y" ....

                            ???

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

                            Comment


                            • #34
                              Originally posted by Michael Mattias View Post
                              or maybe even "SWAP AS LONG x, y" ....
                              Seem a bit on the ugly side.
                              Since the var type is known at compile time, the compiler should be able to infer the optimal way / fastest code to do it.

                              Definitely using SWAP for swapping two array items took far many instructions that swapping two vars (as the timing test clearly shown). For example:

                              Two LONGs, something like:
                              Code:
                              MOV EAX,DWORD PTR [EBP-0104h]
                              XCHG EAX,DWORD PTR [EBP-0100h]
                              MOV DWORD PTR [EBP-0104h],EAX
                              Two items of an array of LONGs, something like:
                              Code:
                              MOV EAX,04h
                              ADD EAX,DWORD PTR [EBP-0178h]
                              MOV EBX,EAX
                              PUSH EBX
                              XOR EAX,EAX
                              ADD EAX,DWORD PTR [EBP-0178h]
                              MOV EBX,EAX
                              POP EDX
                              MOV EAX,DWORD PTR [EBX]
                              XCHG EBX,EDX
                              XCHG EAX,DWORD PTR [EBX]
                              XCHG EBX,EDX
                              MOV DWORD PTR [EBX],EAX
                              Swapping two DOUBLEs is entirely different, and involve calling an utility function:
                              Code:
                              LEA EBX,[EBP-010Ch]
                              LEA EDX,[EBP-0104h]
                              MOV EAX,08h
                              CALL 0403377h ' -- something magical happen here! :-)
                              Bye!
                              -- The universe tends toward maximum irony. Don't push it.

                              File Extension Seeker - Metasearch engine for file extensions / file types
                              Online TrID file identifier | TrIDLib - Identify thousands of file formats

                              Comment


                              • #35
                                Perhaps you could leave the array uninverted* and access the required element with:
                                A$=b$(UBOUND(b$)-requiredelement)
                                Duh.

                                Of course that's the best solution!

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

                                Comment


                                • #36
                                  Here's kind of an interesting (and only 10 ticks if using LONGs) swap of c and b, no temp needed:
                                  Code:
                                  'c and b are any integer type, and could theoretically include float data as integers using pointers.
                                      c = c XOR b
                                      b = b XOR c
                                      c = c XOR b
                                  'or in PB ver. 9:
                                       c XOR= b
                                       b XOR= c
                                       c XOR= b

                                  Comment


                                  • #37
                                    Here's kind of an interesting (and only 10 ticks if using LONGs) swap of c and b, no temp needed
                                    Sounds like a useful "MACRO SwapLong (a, b)"

                                    I'd seen that before, a long time ago. IIRC at the time I drove myself half-silly trying to figure out how/why it worked. But now I can see it clearly.
                                    Michael Mattias
                                    Tal Systems (retired)
                                    Port Washington WI USA
                                    [email protected]
                                    http://www.talsystems.com

                                    Comment


                                    • #38
                                      Wasn't ARRAY SORT in PB9 not being extended with a callback feature?
                                      hellobasic

                                      Comment


                                      • #39
                                        >Wasn't ARRAY SORT in PB9 not being extended with a callback feature?

                                        Yes. It's in the online doc here.

                                        I have not yet ordered my upgrade but I think this one will order earlier than usual.

                                        I've been going really slowly on upgrades since there were 6.11, 7.01, 7.02, 7.03, 7.04, 8.01, 8.02 and 8.03 updates. (I will exempt 8.04 from this list because it was - announcement and version number choice notwithstanding - a major change).

                                        With this many maintenance updates I would have been spending more time re-testing than developing (aka "putting food on the table").

                                        The stability of both 8.03 and apparently 8.04 has convinced me the old quality is back, and I don't need to worry that I'll be installing maintenance updates non-stop.

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

                                        Comment


                                        • #40
                                          Don't get carried away
                                          Afaik you are not an OOP man.
                                          Maybe the other new things may suit you though.
                                          I bought it mainly to keep up to date (PwrDev development), at the office i'll remain using v8 for longer time as before.
                                          (In fact i don't have a need for new things regarding PB at the office)

                                          I like the COM part but i have no idea what to do with it at this time.
                                          No serious things i couldn't do before (i had classes already).
                                          hellobasic

                                          Comment

                                          Working...
                                          X