Re: Generating code which compiles to a jmphash

On Mar 24, 7:20 pm, fvmarcol...@xxxxxxxxx wrote:
Hi,
  I have a number of small utility functions which I would like to
compile
to JMPHASHs (to steal a term from clisp's (disassemble 'foo) output.
Feel free to correct my terminology.)  These functions are called
several million times.  I can and have transformed small, clear
functions
into ugly, hard to maintain case statements.

  A little background:  I'm coding a puzzle solver in my spare time,
for the challenge and as a way to learn lisp.  One part of the solver
is an end-game hash, which takes quite a while to compute.
Turning nice code into ugly code has made the code significantly
faster.

  A simple response of "learn to write macros" probably would not
be inappropriate.  On the other hand, I am at least starting to see
patterns in the code which I know can be abstracted away with macros,
and I'm hoping that a little shove in the right direction will make
that easier.

At the risk of too much information, I'll provide two examples.
Feel free to ignore the first one in your responses.  The first
is included as better example of the kind of transformation
I am interested in, but the second is fairly trivial, and a good
jumping off point for me.

(defconstant dirs '(up down left right))

(defun all-moves ()

  (loop for dir in dirs
     append
       (loop for i from 0 to 4
          collect (list i dir))))

(defun move-to-int (move)
  (+ (first move) (* 5 (position (second move) dirs))))

(nth 12 (all-moves))
       => (2 left)
(map 'list 'move-to-int (all-moves))

       => (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)

On Mar 24, 7:41 pm, fvmarcol...@xxxxxxxxx wrote:
Oops. I accidentially hit send before completing that post...

The problem with the above code is the function move-to-int.
Instead of calling (position ...) every time, I would like code
which compiles to a jmphash, as if I wrote it using case statements.

Here is the second example.

(defun old-char+ (char)
(if (char= char #\9)
#\A
(int-char (1+ (char-int char)))))
vs
(defun char+ (char)
(case char
(#\1 #\2) (#\2 #\3) (#\3 #\4) (#\4 #\5) (#\5 #\6) (#\6 #\7)
(#\7 #\8) (#\8 #\9) (#\9 #\A) (#\A #\B) (#\B #\C) (#\C #\D)
(#\D #\E) (#\E #\F) (#\F #\G) (#\G #\H) (#\H #\I) (t #\*)))

char+ results in a modest 5% improvement in code speed over old-char+.
I really don't care so much about that, or about finding the best
version of char+, but am interested in how you would write code
which given some range of inputs will compile to something similar
to the compiled code for char+.

Thanks. Sorry for the split post.

The 5% difference isn't surprising. Unless the compiler is very
clever, it is going to expand the case into an "if then else" chain
that is not going to run much faster than the (position ) call.

As the lists of values get long, hash tables will eventually be
faster. You can do something like:

CL-USER> (defun hashify (fn domain &key (test #'eql))
(let ((hash (make-hash-table :test test)))
(dolist (val domain hash)
(setf (gethash val hash) (funcall fn val)))))

CL-USER> (defun old-char+ (char)
(if (char= char #\9)
#\A
(code-char (1+ (char-code char)))))

CL-USER> (setq h (hashify #'old-char+ '(#\1 #\2 #\3 #\4 #\5 #\6 #\7 #
\8 #\9
#\A #\B #\C #\D #\E #\F #\G #\H #\I)))/
CL-USER> (gethash #\1 h)
#\2
T

If you are really hard-over on the case idea, then

CL-USER> (defmacro casify (fn domain case-key)
`(case ,case-key
,@(mapcar #'(lambda (x) (list x (funcall fn x)))
domain)))
CASIFY
CL-USER> (macroexpand-1 '(casify 1+ (1 2 3) foo))
(CASE FOO (1 2) (2 3) (3 4))
T
.

Relevant Pages

  • Re: Best way to access this file?
    ... char userType; ... This should not compile due to lacking semicolon ... > class FixedWidthFields ...
    (comp.lang.cpp)
  • Re: freeing memory leads to sig fault
    ... If i have this kind of sudo codeish as i didn't compile it. ... to the freed memory, which may get recycled for other purposes ... char *dosomething ...
    (comp.unix.programmer)
  • LD_PRELOAD odd woes
    ... which I do not have the source code that generates useful information ... static int dyn = 0; ... fopen(const char *path, const char *mode) { ... If I compile this like this: ...
    (comp.os.linux.development.system)
  • Need help to port VAX code to Alpha and to Itaninum
    ... which involves porting kind of stuff from VAX ... Here what I am working project very big and ... But thing is while compile with option I got so many warning ... unsigned long int GEN_TRANS_LOGICAL(char *, ...
    (comp.os.vms)
  • Need help to port VAX code to Alpha and to Itaninum
    ... which involves porting kind of stuff from VAX ... Here what I am working project very big and ... But thing is while compile with option I got so many warning ... unsigned long int GEN_TRANS_LOGICAL(char *, ...
    (comp.os.vms)