Re: make-hash-table :size

[Pascal Bourguignon]

Oliver Scholz <alkibiades@gmx.de> writes:

> Pascal Bourguignon <spam@mouse-potato.com> writes:
> 
> > Kai Grossjohann <kai@emptydomain.de> writes:
> >
> >> Joost Kremers <joostkremers@yahoo.com> writes:
> >> 
> >> > i'm writing a program in emacs that makes rather extensive use of small
> >> > hash tables, about a dozen elemens or so. i'm going over my code again, 
> >> > to
> >> > see if i can improve things here and there, and i suddenly realise that
> >> > MAKE-HASH-TABLE takes a :size argument.
> >> 
> >> I wonder if hash tables are really faster than alists in this case.
> >> Have you tried both?
> >
> > Well, it seems that yes, non-empty emacs hash tables are faster than
> > alists...
> [...]
> 
> For about a dozen elements? I doubt that. I would assume that the
> small overhead in hash key access is likely to make alists more
> efficient for such few elements. And indeed, profiling supports that
> assumption:
> 
> 
> (defconst test-alist
>   (let ((lst (make-list 14 '(lirum . larum))))
>     (append lst '((alpha . beta)))))
> 
> (defconst test-hash
>   (let ((hash (make-hash-table :size 15 :test 'eq)))
>     (puthash 'alpha 'beta hash)
>     hash))
> 
> (defun test-hash-access ()
>   (gethash 'alpha test-hash))
> 
> (defun test-alist-access ()
>   (cdr (assq 'alpha test-alist)))
> 
> 
> (defun test-run ()
>   (interactive)
>   (dolist (func '(test-hash-access test-alist-access))
>     (unless (byte-code-function-p
>            (symbol-function func))
>       (byte-compile func)))
>   (elp-instrument-function 'test-hash-access)
>   (elp-instrument-function 'test-alist-access)
>   (dotimes (ignore-me 10000)
>     (test-hash-access)
>     (test-alist-access))
>   (elp-results))
> 
> 
> On my Emacs 21.3 on a 1.5 GHtz Athlon M-x test-run gives:
> 
> Function Name      Call Count  Elapsed Time  Average Time
> =================  ==========  ============  ============
> test-hash-access   10000       0.09          9e-006
> test-alist-access  10000       0.04          4e-006

Actually, I wrote a more complete benchmark before delivering my conclusion:


--------------------(hash-table.el)--------------------------------------

;; Let's include some CL stuff:
(require 'cl)

(defconstant internal-time-units-per-second 1000000
  "Common-Lisp: Implementation-dependent number of time units in a second.

[cltl2] This value is an integer, the implementation-dependent number of
internal time units in a second. (The internal time unit must be
chosen so that one second is an integral multiple of it.)"
    );;internal-time-units-per-second


(defun pjb-cl%%emacs-time-to-seconds (et)
  "PRIVATE.
PRE:     et is a time in emacs time format, ie. a list ( h l [us])
         with h and l being in [0..65535] and us in [0..999999].
RETURN:  et expressed as a scalar."
  (+ (let ((h (nth 0 et))) (if (< h 1024) (* h 65536) (* h 65536.0)))
     (nth 1 et)
     (let ((us (nth 2 et))) (if (or (null us) (= 0 us)) 0 (/ us 1000000.0))))
  );;pjb-cl%%emacs-time-to-seconds


(defun get-internal-real-time ()
  "Common-Lisp: Current clock time is returned in Internal Time format.

RETURN: The current time is returned as a single integer in Internal
        Time format. This time is relative to an arbitrary time base,
        but the difference between the values of two calls to this
        function will be the amount of elapsed real time between the
        two calls, measured in the units defined by
        internal-time-units-per-second.

NOTE:   Emacs implementation returns the number of micro-seconds
        since 1970-01-01 00:00:00 as a float.
"
  (* internal-time-units-per-second
     (pjb-cl%%emacs-time-to-seconds (current-time)))
  );;get-internal-real-time


(defmacro time (&rest body)
  "Common-Lisp:  time evaluates form in the current environment (lexical and \
dynamic). A call to time can be compiled.
DO:      time prints various timing data and other information to trace output.
         The nature and format of the printed information is
         implementation-defined . Implementations are encouraged to provide
         such information as elapsed real time, machine run time, and storage
         management statistics.
URL: http://www.informatimago.com/local/lisp/HyperSpec/Body/m_time.htm
"
  (let ((start (gensym))
        (result (gensym))
        (stop (gensym))
        (time (gensym)))
    `(let* ( (,start  (get-internal-real-time))
             (,result (progn ,@body))
             (,stop   (get-internal-real-time)) 
             (,time   (- ,stop ,start)) )
       (princ (format  "Time: %12.3f µs" ,time)))));;time


;; The meat of the benchmark:

(defparameter +repeat+ 1000)

(defun hash-fill  (size test)
  (let ((table (make-hash-table :test test :size size)))
    (dotimes (i size) (setf (gethash (format "%d" i) table) i))
    table))

(defun hash-get-keys (table)
  (let ((keys '()))
    (maphash (lambda (k v) (push k keys)) table)
    keys))

(defun hash-fetch (table test key)  (gethash key table))

(defun alist-fill  (size test)
  (let ((alist '()))
    (dotimes (i size) (push (cons (format "%d" i) i) alist))
    alist))

(defun alist-get-keys (alist)   (mapcar (function car) alist))

(defun alist-fetch (table test key)  (assoc key table :test test))

(defun tally ()
  (dotimes (size 15)
    (dolist (test '(eq eql equal))
      (dolist (cl '((hash-fill  hash-get-keys  hash-fetch  :hash)
                    (alist-fill alist-get-keys alist-fetch :alist)))
        (let* ((compound (funcall (first cl) size test))
               (keys     (funcall (second cl) compound)))
          (princ (format "%20s" (list (fourth cl) size test)))
          (time
           (dotimes (i +repeat+)
             (dolist (k keys)  (funcall (third cl) compound test k))
             (dotimes (k size) (funcall (third cl) compound test k))))
          (terpri))) (terpri)) (terpri)));;tally


;; end of hash-table.el


(progn (byte-compile-file "hash-table.el")
       (load-file "hash-table.elc")
       (setf +repeat+ 10000)
       (tally))

==>

        (:hash 0 eq)Time:     9519.125 µs
       (:alist 0 eq)Time:     9780.250 µs

       (:hash 0 eql)Time:     9074.875 µs
      (:alist 0 eql)Time:    89049.125 µs

     (:hash 0 equal)Time:   159119.125 µs
    (:alist 0 equal)Time:     9649.125 µs


        (:hash 1 eq)Time:    39810.000 µs
       (:alist 1 eq)Time:   581610.000 µs

       (:hash 1 eql)Time:    47351.125 µs
      (:alist 1 eql)Time:   509031.125 µs

     (:hash 1 equal)Time:    76388.875 µs
    (:alist 1 equal)Time:   471781.000 µs


        (:hash 2 eq)Time:    89989.000 µs
       (:alist 2 eq)Time:   904411.125 µs

       (:hash 2 eql)Time:   112393.000 µs
      (:alist 2 eql)Time:  1076395.000 µs

     (:hash 2 equal)Time:   110723.875 µs
    (:alist 2 equal)Time:  1403409.000 µs


        (:hash 3 eq)Time:   157952.125 µs
       (:alist 3 eq)Time:   992513.875 µs

       (:hash 3 eql)Time:   118767.000 µs
      (:alist 3 eql)Time:  1898227.000 µs

     (:hash 3 equal)Time:   119163.000 µs
    (:alist 3 equal)Time:  1825305.000 µs


        (:hash 4 eq)Time:   225544.875 µs
       (:alist 4 eq)Time:  1772409.000 µs

       (:hash 4 eql)Time:   183063.000 µs
      (:alist 4 eql)Time:  1964644.000 µs

     (:hash 4 equal)Time:   195405.875 µs
    (:alist 4 equal)Time:  2681090.750 µs


        (:hash 5 eq)Time:   239486.875 µs
       (:alist 5 eq)Time:  2732085.000 µs

       (:hash 5 eql)Time:   203306.875 µs
      (:alist 5 eql)Time:  2946955.000 µs

     (:hash 5 equal)Time:   248938.125 µs
    (:alist 5 equal)Time:  3488260.000 µs


        (:hash 6 eq)Time:   242912.125 µs
       (:alist 6 eq)Time:  2372359.000 µs

       (:hash 6 eql)Time:   252884.875 µs
      (:alist 6 eql)Time:  3490458.000 µs

     (:hash 6 equal)Time:   274726.875 µs
    (:alist 6 equal)Time:  4264734.000 µs


        (:hash 7 eq)Time:   683985.875 µs
       (:alist 7 eq)Time:  2923297.875 µs

       (:hash 7 eql)Time:   321365.125 µs
      (:alist 7 eql)Time:  4333614.750 µs

     (:hash 7 equal)Time:   322398.000 µs
    (:alist 7 equal)Time:  4733676.250 µs


        (:hash 8 eq)Time:   348424.875 µs
       (:alist 8 eq)Time:  3196606.875 µs

       (:hash 8 eql)Time:   379910.000 µs
      (:alist 8 eql)Time:  6019358.875 µs

     (:hash 8 equal)Time:   381468.000 µs
    (:alist 8 equal)Time:  6545720.125 µs


        (:hash 9 eq)Time:   418741.000 µs
       (:alist 9 eq)Time:  3517043.750 µs

       (:hash 9 eql)Time:   410253.000 µs
      (:alist 9 eql)Time:  5796592.250 µs

     (:hash 9 equal)Time:   949384.875 µs
    (:alist 9 equal)Time:  6860958.125 µs


       (:hash 10 eq)Time:   439682.000 µs
      (:alist 10 eq)Time:  3974476.125 µs

      (:hash 10 eql)Time:   465018.000 µs
     (:alist 10 eql)Time: 13181789.125 µs

    (:hash 10 equal)Time:  1056310.250 µs
   (:alist 10 equal)Time: 10347398.000 µs


       (:hash 11 eq)Time:   525230.250 µs
      (:alist 11 eq)Time:  4749943.125 µs

      (:hash 11 eql)Time:   500923.125 µs
     (:alist 11 eql)Time: 10596731.875 µs

    (:hash 11 equal)Time:   528394.000 µs
   (:alist 11 equal)Time:  9048454.125 µs


       (:hash 12 eq)Time:  1025217.000 µs
      (:alist 12 eq)Time:  5466906.125 µs

      (:hash 12 eql)Time:   523550.000 µs
     (:alist 12 eql)Time:  8851365.125 µs

    (:hash 12 equal)Time:   536098.000 µs
   (:alist 12 equal)Time:  9239335.125 µs


       (:hash 13 eq)Time:   574123.000 µs
      (:alist 13 eq)Time:  5268079.000 µs

      (:hash 13 eql)Time:   568025.750 µs
     (:alist 13 eql)Time: 10765734.875 µs

    (:hash 13 equal)Time:   564960.000 µs
   (:alist 13 equal)Time:  9361194.125 µs


       (:hash 14 eq)Time:   585877.000 µs
      (:alist 14 eq)Time:  5390757.125 µs

      (:hash 14 eql)Time:   635772.000 µs
     (:alist 14 eql)Time: 12009460.000 µs

    (:hash 14 equal)Time:   677022.875 µs
   (:alist 14 equal)Time: 14172797.000 µs


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.