Fast hex conversion (followup)

[John Gleason]

I made two other optimizations to Dave Roberts' code here: http://www.powerbasic.com/support/pb...388#post280388, and lately I've been using Dave's timer a lot too (hey, I added one or two lines of code in there, just pull out a magnifying glass and you'll find them)

#COMPILE EXE
#DIM ALL
DECLARE FUNCTION QueryPerformanceCounter LIB "KERNEL32.DLL" ALIAS "QueryPerformanceCounter" (lpPerformanceCount AS QUAD) AS LONG
DECLARE FUNCTION QueryPerformanceFrequency LIB "KERNEL32.DLL" ALIAS "QueryPerformanceFrequency" (lpFrequency AS QUAD) AS LONG

'~~~~~~~~~~~A Variation of Dave Roberts' MACRO Timer~~~~~~~~~~~~~~~~~~~~~~~
MACRO onTimer
  LOCAL qFreq, qOverhead, qStart, qStop AS QUAD
  LOCAL f AS STRING
  f = "#.###"
  QueryPerformanceFrequency qFreq
  QueryPerformanceCounter qStart ' Intel suggestion. First use may be suspect
  QueryPerformanceCounter qStart ' So, wack it twice <smile>
  QueryPerformanceCounter qStop
  qOverhead = qStop - qStart     ' Relatively small
END MACRO

MACRO goTimer = QueryPerformanceCounter qStart
MACRO stopTimer = QueryPerformanceCounter qStop

MACRO showTimer = USING$(f,(qStop - qStart - qOverhead)*1000000/qFreq /1000) + " milliseconds"
'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

FUNCTION PBMAIN () AS LONG

  DIM hashByte() AS BYTE
  DIM hashByteHex () AS STRING * 2
  DIM hashByteHexW () AS WORD       'use fast intrinsic WORD type rather than STRING * 2
  DIM hexArr(255) AS WORD
  LOCAL hashText AS STRING
  LOCAL hashSize, i AS LONG

  hashSize = 3200000 ' bytes for example
  
  FOR i = 0 TO 255                  'pre-calculate the hex translation array to avoid the HEX$() conversion later
     hexArr(i) = CVWRD(HEX$(i, 2))
  NEXT

  REDIM hashByte(hashSize -1) AS BYTE

  FOR i = 0 TO hashSize- 1
    hashByte(i) = RND(0,255) ' Output from a hashing algorithm, for example
  NEXT

  hashText = SPACE$(2*hashSize)
  REDIM hashByteHex( hashSize - 1)  AS STRING * 2 AT STRPTR(hashText)
  REDIM hashByteHexW( hashSize - 1) AS WORD       AT STRPTR(hashText)

  onTimer
  goTimer
  FOR i = 0 TO hashSize-1
    hashByteHex(i) =   HEX$( hashByte( i ),2 )   'comment each line out in turn to compare speed
'   hashByteHexW(i) = hexArr( hashByte( i )   )  'comment each line out in turn to compare speed
  NEXT
  stopTimer

  MSGBOX showTimer & $CRLF & $CRLF & RIGHT$(hashText, 2000)

END FUNCTION

[David Roberts]

Mind boggling.

Of course, the Hex$ conversion is not being avoided.

You are effectively creating a look-up table and its creation overhead is more than offset by HEX$(i, 2) being faster to read than HEX$( hashByte( i ),2 ) or, more to the point, reading 'i' is faster than reading 'hashByte( i )'.

Your code illustrates the use of some of the PowerBASIC commands which we all read on getting the compiler manual and wonder what on earth they'd be used for and then promptly forget they exist. It is probably worthwhile for a lot of us to sit down quietly sometime and browse through the commands again. No doubt some of us will find ourselves saying "That didn't make much sense the first time that I read that but, Oh boy, do I have a use for it now."

I'm not keen on your alterations to my timer macro.

I may be nitpicking but 'Dave Roberts' MACRO Timer' should read 'A variation of Dave Roberts' MACRO Timer'.

OnTimer suggests to me that maybe an OffTimer exists and some tidying up is required. My InitializeTimer is clearly a one off statement. Perhaps SetUpTimer would be a better term.

As for the goTimer/stopTimer pair rather than my StartTimer/StopTimer pair I see that as traffic lights compared to a stopwatch. I'll stay withh the stopwatch.


The '*1000000/qFreq /1000' is effectively the same as my '*1000/qFreq' with redundancy. I guess you were tweaking there and forgot to tidy up.

I am now declaring qFreq, and so on, as Globals so that the associated macros may be used in functions.

[John Gleason]

I'll update my post above to note the timer macro is a (slight) variation.

As for the goTimer/stopTimer pair rather than my StartTimer/StopTimer

I only changed the names because I use it so much I wanted them as short as possible and still make some sense.
And the extra /1000 gives milli and microseconds without having to count thru any digits. My computer is only accurate to +- a few microsecs using the performanceCounter anyway, so that resolution is enough to cover it.

Also, here is a hard-coded look-up table for to use instead of that much slower HEX$ loop:

  ARRAY ASSIGN hexArr() = &h3030, _
     &h3130,&h3230,&h3330,&h3430,&h3530,&h3630,&h3730,&h3830,&h3930,&h4130,&h4230,&h4330,&h4430,&h4530,&h4630,&h3031, _
     &h3131,&h3231,&h3331,&h3431,&h3531,&h3631,&h3731,&h3831,&h3931,&h4131,&h4231,&h4331,&h4431,&h4531,&h4631,&h3032, _
     &h3132,&h3232,&h3332,&h3432,&h3532,&h3632,&h3732,&h3832,&h3932,&h4132,&h4232,&h4332,&h4432,&h4532,&h4632,&h3033, _
     &h3133,&h3233,&h3333,&h3433,&h3533,&h3633,&h3733,&h3833,&h3933,&h4133,&h4233,&h4333,&h4433,&h4533,&h4633,&h3034, _
     &h3134,&h3234,&h3334,&h3434,&h3534,&h3634,&h3734,&h3834,&h3934,&h4134,&h4234,&h4334,&h4434,&h4534,&h4634,&h3035, _
     &h3135,&h3235,&h3335,&h3435,&h3535,&h3635,&h3735,&h3835,&h3935,&h4135,&h4235,&h4335,&h4435,&h4535,&h4635,&h3036, _
     &h3136,&h3236,&h3336,&h3436,&h3536,&h3636,&h3736,&h3836,&h3936,&h4136,&h4236,&h4336,&h4436,&h4536,&h4636,&h3037, _
     &h3137,&h3237,&h3337,&h3437,&h3537,&h3637,&h3737,&h3837,&h3937,&h4137,&h4237,&h4337,&h4437,&h4537,&h4637,&h3038, _
     &h3138,&h3238,&h3338,&h3438,&h3538,&h3638,&h3738,&h3838,&h3938,&h4138,&h4238,&h4338,&h4438,&h4538,&h4638,&h3039, _
     &h3139,&h3239,&h3339,&h3439,&h3539,&h3639,&h3739,&h3839,&h3939,&h4139,&h4239,&h4339,&h4439,&h4539,&h4639,&h3041, _
     &h3141,&h3241,&h3341,&h3441,&h3541,&h3641,&h3741,&h3841,&h3941,&h4141,&h4241,&h4341,&h4441,&h4541,&h4641,&h3042, _
     &h3142,&h3242,&h3342,&h3442,&h3542,&h3642,&h3742,&h3842,&h3942,&h4142,&h4242,&h4342,&h4442,&h4542,&h4642,&h3043, _
     &h3143,&h3243,&h3343,&h3443,&h3543,&h3643,&h3743,&h3843,&h3943,&h4143,&h4243,&h4343,&h4443,&h4543,&h4643,&h3044, _
     &h3144,&h3244,&h3344,&h3444,&h3544,&h3644,&h3744,&h3844,&h3944,&h4144,&h4244,&h4344,&h4444,&h4544,&h4644,&h3045, _
     &h3145,&h3245,&h3345,&h3445,&h3545,&h3645,&h3745,&h3845,&h3945,&h4145,&h4245,&h4345,&h4445,&h4545,&h4645,&h3046, _
     &h3146,&h3246,&h3346,&h3446,&h3546,&h3646,&h3746,&h3846,&h3946,&h4146,&h4246,&h4346,&h4446,&h4546,&h4646

[Michael Mattias]

Hex pairs==>bytes and bytes==>hex pairs

http://www.powerbasic.com/support/pbforums/showthread.php?t=25176

Note not the same thing as reading/writing MKI$ or MKWRD$ strings but easily adaptable to same.

Of course, you'd never read a string of MKI$ or MKWRD$ strings, you'd...

REDIM Foo(LEN(string)\2-1) AS INTEGER|WORD AT STRPTR(string)

[David Roberts]

I have just realised that Gary Barnes sneaked the 1000000 into the macro. My opening post used 1000.

John, your code is now getting so close to light speed it is in serious danger of evaporating.

[David Roberts]

The cameras are rolling and you are just about to put the flag up when someone chips in with "So, whose footprint is that then?". Oh, dear.

[Gary Barnes]

I didn't sneak it in
I wanted the result in micro seconds to measure how long the sleep instruction takes. I thought that it might be instructive to post it.
I humbly seek your forgiveness David for sullying the purity of your post

[David Roberts]

I don't do purity, Gary. At my age I figured I should at least be able see it on the horizon. I think that is the best that I can hope for now.

[John Gleason]

I thought that it might be instructive

and indeed it was. For some reason, I used to think SLEEP had only like 50 milliSec resolution and never thought to test it. Now I know that except for maybe 1,2,3,4 which all seem to be around 3 or 4mSec, it is pretty much right on the millisecond.

[Gary Barnes]

Cheers David

[David Roberts]

Before I forget, I've added 'Macro nTimeTaken = Val(TimeTaken)' to the macro so we could have, for example:

tot = tot + nTimeTaken

or Macro nshowTimer = Val(showTimer) in John's variant.