Binary search - speeding things up

[The Beez]

Hi 4tH-ers!

Normally, the 4tH preprocessor is speedy enough, but sometimes, there is a noticeable delay. Not enough to irritate you, but still.

So I wondered if I could speed things up by applying binary search with some lookup tables. But would it do enough?

Well, I decided to test the thing, took a long (200+ entries) table and started a long line of random lookups (>100,000). Then I calculated the speedup the use of binary search achieved.

The first graph shows you the speedup. With 200 elements, it's over 7 times as fast. The "cutt-off" point is around 10 elements. A lower number of elements and binary search is even slower. The graph passes the "two times faster" line at 50 elements.

The second one shows the number of milliseconds to do a search. The binary search line is almost flat (even flatter than I expected) while the sequential search is exponential (as expected). 

BOTTOMLINE: You're crazy NOT to use binary search if you have more than 50 elements. Between 25 and 50 elements it really depends on how often the table is searched, but don't expect any miracles. Below 25, just do a sequential search.

In PP4TH the biggest table counts 45 elements. That's just in between, so I figured it wouldn't be worth the trouble - because binary search is hard to set up (may be I ought to make that easier).

Finally, for your listening pleasure, the code (minus the table).

include lib/bsearch.4th

include lib/row.4th

include lib/anstools.4th

include lib/choose.4th

64 string (search-key) does> >r r@ place r> ;

create Brands                          \ tabel met toegestane merknamen

(...)

  here Brands - constant #Brands

  NULL ,

: bsBrands                              ( a1 n1 a2 n2 -- a3 f)

  ['] b-compare defer@ >r ['] get-key defer@ >r

  :noname swap cells + @c ; is get-key \ key-retrieval functie

  :noname >r count r> count compare ; is b-compare  

  >r >r (search-key) r> r> bsearch 

  r> is get-key r> is b-compare        \ perform a binary search

;

                                       ( a1 n1 a2 -- a1 n1 a3 f)

: sqBrands >r (search-key) count r> 1 string-key row ;

: rndBrand Brands #Brands choose cells + @c count ;

: rndBs rndBrand Brands #Brands bsBrands drop drop ;

: rndSq rndBrand Brands sqBrands drop drop 2drop ;

: testBs 0 ?do rndBs loop ;

: testSq 0 ?do rndSq loop ;

#Brands . cr

400000 testSq

Hans Bezemer 

[The Beez]

Hi 4tH-ers!

 

That's why you do things like this: uBasic has about 60 keywords and with every single token they are checked. So I applied my binary search patch. About 80 opcodes, clean replace, worked first time, 1.6 times faster (about 40% increase). BAM!

Hans Bezemer

[The Beez]

Hi 4tH-ers!

I told you: "maybe I ought to make things easier:. And I did. I created the BROW library, which is very close to the ROW library. Note: keep your tables sorted! I banged into that one while debugging :-(

Differences:

- ROW has a terminator, this one needs a count;

- ROW returns the search value. You have to take care of that yourself (e.g. by a DUP or 2DUP;

- You have to use :REDO if you want to bind it to the table, because the count is the last definition compiled.

Hans Bezemer

\ TYPICAL USE:

\ ============

\ create mystable

\   ," Aloha" 4 ,

\   ," Bye"   3 ,

\   ," Doei"  5 ,

\   ," Hello" 1 ,

\   here mystable - 2 / constant /mystable

\ create myntable

\   0 , 1 ,

\   1 , 3 ,

\   2 , 5 ,

\   3 , 7 ,

\   4 , 9 ,

\   here myntable - 2 / constant /myntable

\ s" Aha"      mystable /mystable 2 bstring-key brow . . . cr

\ s" Aloha"    mystable /mystable 2 bstring-key brow . . . cr

\ s" Bye"      mystable /mystable 2 bstring-key brow . . . cr

\ s" Hello"    mystable /mystable 2 bstring-key brow . . . cr

\ s" Gutentag" mystable /mystable 2 bstring-key brow . . . cr cr

\ -1 myntable /myntable 2 bnum-key brow . . . cr

\  0 myntable /myntable 2 bnum-key brow . . . cr

\  2 myntable /myntable 2 bnum-key brow . . . cr

\  4 myntable /myntable 2 bnum-key brow . . . cr

\  6 myntable /myntable 2 bnum-key brow . . . cr

\ NOTE: ALL TABLES MUST BE PROPERLY SORTED!!

[The Beez]

Hi 4tH-ers!

Since adding binary search to uBasic was a success I wondered whether further use of this algorithm would enhance the performance even more.

But there was one difference - these were not text searches, it were integer searches. And would those have a similar behavior?

As always, the only way was to try it out. And I was right. They were different. Where TEXT searches would benefit even at a relatively low number of elements, INTEGER searches do that much later:

It will be useful to switch to binary search after about 32 elements. That meant that converting all of uBasic tables would render little effect. Still, it's quite useful to know.

Hans Bezemer

[The Beez]

Hi 4tH-ers!

I've added a second library to make binary search tables a bit easier, called BSTABLE.4TH. You can turn an array into a binary search table with a key and a value. Yes, we already had one for associated arrays, but this one is more bare bones to allow you to build your own variant much more easily.

You can insert a key, delete a key and search for a key and some utility words to calculate real addresses (most words work with "entries") or get to the value part.

As usual code in SVN, although it seems to suffer a bit from a DDOS attack since yesterday.

Hans Bezemer