Stack Exchange
Speeding Up a Function Involving String Searches
I have one function that profiling shows consumes most of the run time. Is there perhaps a way to rethink this for a substantial speedup? (Running Common Lisp in SBCL)
(defun compatible-words (option1 option2)
  ;Determines if two field+word fillings are compatible.
  (destructuring-bind (field1 word1) option1
    (destructuring-bind (field2 word2) option2
      (destructuring-bind (index1 index2) (or (gethash (list field1 field2) *crosscuts-ht*)
                                              '(nil nil))
        (or (null index1) (char= (schar word1 index1) (schar word2 index2)))))))

(ps: Adding declarations seems to have minimal effects.)
Edit: Sorry about not providing some context for analysis. Option1 & option2 are 2-item lists of a symbol and a simple-string. String length is a max of ~50 uppercase alphabetic chars, with an average of ~7 chars. Thus index1 & index2 can be fixnums, and *crosscuts-ht* is an #'equal hashtable with keys as lists of 2 symbols. Hashtable values are lists of the 2 indexes.

It's difficult to optimize a function that just destructures, gethash and do 1 comparison, without knowing what calls it and how it calls it. And without having the declaration of crosscuts-ht. I guess you defined crosscuts-ht with :test #'equalp ?

Do you have a maximum size limit for your strings ? do you have constraints on what fields are? is there a constant list of fields? maybe you can add more details about your constraints to help with data representation (e.g. index1 and index2 could be two 16bit integers packed in a 32bit integer, etc.)

If the strings have a size of at most 50, you can round that to 64, ie. 6 bits (or 8 bits, something most architectures are more optimized to access), making the pair of indices fit in 12 bits (resp. 16).
If each field is a symbol, you could maybe associate a single index to it at creation time, e.g. in its symbol-value, from 0 to N. And your lookup table could be an NxN matrix of (unsigned-byte 12) or (unsigned-byte 16) integers.
This may improve your lookup time.
If the list of symbols grows dynamically, is too large and/or the matrix is sparse, you probably want to keep the hash-table.

Interesting idea. The field symbols don't change in each run, and the max matrix size would be only a little over 1000 entries. They would be rather sparse at an average of about 15%, but that's no problem. As I'm (currently) unfamiliar with byte manipulations, can you show how to pack and unpack a couple of nonnegative fixnums into (unsigned-byte 16)? Also, since space is not an issue, is there a major time advantage of using byte entries over a simple dotted list of two fixnum indices? Thanks.

@davypough you would need to use DDB (resp. LPB) to pack (resp. unpack) the integers. For example: (dpb 3 (byte 8 8) (dpb 5 (byte 8 0) 0)) is #b0000001100000101; you could also use ASH and LOGIOR like << and | in C (logior (ash 3 8) 5)

(defun compatible-words (option1 option2)
  (destructuring-bind (index1 index2) (gethash (list (car option1) (car option2)) *crosscuts-ht* '(nil nil))
    (or (null index1) (char= (schar (cadr option1) index1) 
                             (schar (cadr option2) index2)))))

I eliminated 2 destructuring binds by using car and cadr instead.
Without having to test it it is clear that car nd cadr will be faster since super cheap.
I eliminated one or by giving '(nil nil) as default to gethash.
Further, you could type index to gain speed:
(defun compatible-words (option1 option2)
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum index1 index2))
  (multiple-value-bind (index1 index2) (gethash (list (cadr option1) (cadr option2)) *crosscuts-ht* '(nil nil))
    (or (null index1)
        (char= (schar option1 index1)
               (schar option2 index2))))))


It should be faster, in theory. It would be nice to compare timings, because implementations optimize code sometimes in an unintuitive manner.

I'm getting some unintuitive testing results here. First, running your algorithmic improvements with and without declarations produces negligible timing differences (within ~1%) on SBCL. Correct me if I'm wrong, but it looks like SBCL does a good job of optimizing without any declarations at all.

Second, comparing your version with mine--but changing your multiple-value-bind to destructuring-bind, and gethash default to (-1 -1)--I again get minimal variation (but yours is about ~2% faster). I guess my conclusion is that tinkering is, more often than not, ineffective, at least in SBCL. The best time is spent on rethinking the algorithm. Agree or disagree?

@davypough I agree. I didn't expect huge gains from this.
