Sunday, August 30, 2020

I C how to make things smaller and faster ...

 The wirdz Scrabble® Solver has gone through a number of iterations:

1. The original solver  "simply" used SQL against the MySQL database to find matching words including wild cards.  It was quite a challenge to get this to work quickly enough to deliver results in an acceptable time but even so, the CPU load was quite noticeable.  Certainly not scalable and the SQL was certainly not simple.

2. A python in-memory solver.  This was definitely faster although it needed vectorised numpy operations to achieve an acceptable performance as Python's interpreted loops and run-time object type operations make any implementation of directly coded loops and checks pretty slow.  This used XMLRPC as the request/response protocol.

3. An implementation in the Julia language, which uses a compile on demand/lazy compile approach.  This was definitely faster but there appears to be no such thing as a small memory footprint Julia program due to the size of the run-time libraries including the compiler functions.  The Julia program provided a REST interface.

4. Finally (?), the Scrabble Solver is written in C and operates as a fully in-memory process (once the word tables have been initially loaded from the DB).  This is small and fast and now includes the option to use template patterns to reflect the existing board position.  It also allows double and triple letter and word scores to be specified and taken into account when determining the highest scoring plays.

To provide the same functionality as the Julia program, the C version is about 60% longer (in lines).  Not a lot when additional closing brackets ("}") are needed as well as more code intensive operations to allocate and free heap memory (malloc & free) and relatively clunky string operations.

The C version uses the PCRE regex library to do fast pattern matching and the GNU libmicrohttpd library to provide the REST server framework.

Needless to say it's both faster and much smaller 😊.

The original Scrabble Solver is still at its original url (wirdz Scrabble Solver).  The new Scrabble Helper which includes pattern matching is at (wirdz Scrabble Helper).






0 Comments:

Post a Comment

<< Home