Prev: SBCL optimization
Next: what do lispers think of bigtable?
From: Captain Obvious on 17 Jan 2010 06:38
RU> as the key. It conses on every hash lookup, but if that's
RU> acceptable...

It is pretty easy to avoid consing, in single threaded case, at least.

(let ((the-cons (cons nil nil)))
(defun lookup-compound-key (ht k1 k2)
(setf (car the-cons) k1
(cdr the-cons) k2)
(prog1
(gethash the-cons ht)
(setf (car the-cons) nil
(cdr the-cons) nil))))

Thread-safe solution would probably require thread-local variables.


From: Nicolas Neuss on 17 Jan 2010 08:54
"Captain Obvious" <udodenko(a)users.sourceforge.net> writes:

> It is pretty easy to avoid consing, in single threaded case, at least.
>
> (let ((the-cons (cons nil nil)))
> (defun lookup-compound-key (ht k1 k2)
> (setf (car the-cons) k1
> (cdr the-cons) k2)
> (prog1
> (gethash the-cons ht)
> (setf (car the-cons) nil
> (cdr the-cons) nil))))
>
> Thread-safe solution would probably require thread-local variables.

Hmm, Wasn't it you who wrote three minutes before this message:

> There is no such thing as "too inefficient". Just do whatever is
> convenient, and later, _if_ performance is a problem, you can optimize
> it.

And now you write such an ugly mess without any need?

Nicolas
From: Captain Obvious on 17 Jan 2010 09:05

NN> Hmm, Wasn't it you who wrote three minutes before this message:

??>> There is no such thing as "too inefficient". Just do whatever is
??>> convenient, and later, _if_ performance is a problem, you can optimize
??>> it.

NN> And now you write such an ugly mess without any need?

I'm just showing an interesting technique which, I think, can be useful
in some cases. But I'm not recommend to use it unless you absolutely
need it and know what you're doing. I thought that my message about
premature optimization should make it clear so I did not bother with
additional warnings.

By the way, as you call it an ugly mess, is there a better way to do it?
Like, make cons stack-allocated via some dynamic-extend declaration
or something. Do such things work?


From: Tamas K Papp on 17 Jan 2010 09:32
On Sun, 17 Jan 2010 13:38:57 +0200, Captain Obvious wrote:

> RU> as the key. It conses on every hash lookup, but if that's
> RU> acceptable...
>
> It is pretty easy to avoid consing, in single threaded case, at least.
>
> (let ((the-cons (cons nil nil)))
> (defun lookup-compound-key (ht k1 k2)
> (setf (car the-cons) k1
> (cdr the-cons) k2)
> (prog1
> (gethash the-cons ht)
> (setf (car the-cons) nil
> (cdr the-cons) nil))))
>
> Thread-safe solution would probably require thread-local variables.

Dude, it is still mid-January, but you are very likely to win the
"Optimization of the Year Award" in 2010: it is ugly, and results in a
much longer runtime.

(let ((the-cons (cons nil nil)))
(defun ugly-lookup (ht k1 k2)
(setf (car the-cons) k1
(cdr the-cons) k2)
(prog1
(gethash the-cons ht)
(setf (car the-cons) nil
(cdr the-cons) nil))))

(defun lookup (ht k1 k2)
(gethash (cons k1 k2) ht))

(defparameter *ht* (make-hash-table :test #'equal))
(setf (gethash (cons 5 10) *ht*) 5)

(time
(dotimes (i 10000000)
(lookup *ht* 5 10)))

Evaluation took:
0.923 seconds of real time
0.920058 seconds of total run time (0.916058 user, 0.004000 system)
[ Run times consist of 0.020 seconds GC time, and 0.901 seconds non-GC
time. ]
99.67% CPU
2,330,460,770 processor cycles
80,068,320 bytes consed

(time
(dotimes (i 10000000)
(ugly-lookup *ht* 5 10)))

Evaluation took:
3.464 seconds of real time
3.452216 seconds of total run time (3.452216 user, 0.000000 system)
99.65% CPU
8,753,522,082 processor cycles
354,272 bytes consed

I really wish that people who post "optimized" CL code would at least
benchmark it.

Tamas
From: piscesboy on 17 Jan 2010 10:47
On Jan 17, 9:32 am, Tamas K Papp <tkp...(a)gmail.com> wrote:
> On Sun, 17 Jan 2010 13:38:57 +0200, Captain Obvious wrote:
> > RU> as the key.  It conses on every hash lookup, but if that's
> >  RU> acceptable...
>
> > It is pretty easy to avoid consing, in single threaded case, at least.
>
> > (let ((the-cons (cons nil nil)))
> >   (defun lookup-compound-key (ht k1 k2)
> >     (setf (car the-cons) k1
> >             (cdr the-cons) k2)
> >     (prog1
> >            (gethash the-cons ht)
> >            (setf (car the-cons) nil
> >                    (cdr the-cons) nil))))
>
> > Thread-safe solution would probably require thread-local variables.
>
> Dude, it is still mid-January, but you are very likely to win the
> "Optimization of the Year Award" in 2010: it is ugly, and results in a
> much longer runtime.
>
> (let ((the-cons (cons nil nil)))
>   (defun ugly-lookup (ht k1 k2)
>     (setf (car the-cons) k1
>           (cdr the-cons) k2)
>     (prog1
>         (gethash the-cons ht)
>       (setf (car the-cons) nil
>             (cdr the-cons) nil))))
>
> (defun lookup (ht k1 k2)
>   (gethash (cons k1 k2) ht))
>
> (defparameter *ht* (make-hash-table :test #'equal))
> (setf (gethash (cons 5 10) *ht*) 5)
>
> (time
>  (dotimes (i 10000000)
>    (lookup *ht* 5 10)))        
>
> Evaluation took:
>   0.923 seconds of real time
>   0.920058 seconds of total run time (0.916058 user, 0.004000 system)
>   [ Run times consist of 0.020 seconds GC time, and 0.901 seconds non-GC
> time. ]
>   99.67% CPU
>   2,330,460,770 processor cycles
>   80,068,320 bytes consed
>
> (time
>  (dotimes (i 10000000)
>    (ugly-lookup *ht* 5 10)))
>
> Evaluation took:
>   3.464 seconds of real time
>   3.452216 seconds of total run time (3.452216 user, 0.000000 system)
>   99.65% CPU
>   8,753,522,082 processor cycles
>   354,272 bytes consed
>
> I really wish that people who post "optimized" CL code would at least
> benchmark it.
>
> Tamas

Strange. The ugly cons lookup had 354,272 bytes consed, yet took 3.464
seconds to execute. But the pretty lookup had 80,068,320 bytes consed
and took fewer processor cycles in 0.923 seconds.

The ugly cons had fewer bytes consed than the pretty cons...?
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: SBCL optimization
Next: what do lispers think of bigtable?