make-hash-table :size

make-hash-table :size

[Joost Kremers]

hi all,

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.

so i start wondering, will i gain anything by defining my hash tables with
(make-hash-table :size 15)? does it save memory, will it speed things up?
or is it really moot whether i specify a size of 15 or let emacs just use
the default size of 65? i've tried to find some discussion of this issue on
the net, but google didn't reveal much.

TIA

-- 
Joost Kremers                                      joostkremers@yahoo.com
Selbst in die Unterwelt dringt durch Spalten Licht
EN:SiS(9)

Re: make-hash-table :size

[Stefan Monnier]

> so i start wondering, will i gain anything by defining my hash tables with
> (make-hash-table :size 15)? does it save memory, will it speed things up?

It might do both.  But as always, this is strongly dependent on what your
code does, so you'll have to measure it yourself.

The expectation is that specifying a (mostly correct) size should only make
things better.  If it makes things worse, then it might be considered as
a bug.


        Stefan

Re: make-hash-table :size

[Joost Kremers]

Stefan Monnier wrote:
>> so i start wondering, will i gain anything by defining my hash tables with
>> (make-hash-table :size 15)? does it save memory, will it speed things up?
>
> It might do both.  But as always, this is strongly dependent on what your
> code does, so you'll have to measure it yourself.
>
> The expectation is that specifying a (mostly correct) size should only make
> things better.  If it makes things worse, then it might be considered as
> a bug.

ok, thanks for the info. i'll just put it in, then, and if i see some
terrible degradation in performance, i'll know what first to try...

-- 
Joost Kremers                                      joostkremers@yahoo.com
Selbst in die Unterwelt dringt durch Spalten Licht
EN:SiS(9)

Re: make-hash-table :size

[Kai Grossjohann]

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?

Kai

Re: make-hash-table :size

[Pascal Bourguignon]

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...

-- 
__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.

Re: make-hash-table :size

[Oliver Scholz]

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



    Oliver
-- 
13 Fructidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

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.

Re: make-hash-table :size

[Oliver Scholz]

Pascal Bourguignon <spam@mouse-potato.com> writes:

> Oliver Scholz <alkibiades@gmx.de> writes:

[hash tables vs. alist for about a dozen elements.]
]
>> 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:

The completeness wouldn't explain the differences. I wouldn't trust
the actual times provided by the Emacs Lisp profiler, but the relative
times should be similar in both your benchmark and mine. Obviously, I
do not doubt your results, but I'd say that the differences request
explanation; and I am curious about their reason.

Actually I couldn't get your code to run:

> --------------------(hash-table.el)--------------------------------------
>
> ;; Let's include some CL stuff:
> (require 'cl)
>
> (defconstant internal-time-units-per-second 1000000
[...]

AFAICS `defconstant' doesn't exist, not even in cl.el.  But more
importantly:

[...]
> (defun alist-fetch (table test key)  (assoc key table :test test))

This `assoc' is not an Emacs function. There does exist an cl.el
function with such a parameter specification, but this one is called
`assoc*'.

I assume that you use some extended CL compatibility package other
than the one that comes with stock Emacs?  If that one overwrites
Emacs' `assoc' (which is implemented in C) with a function implemented
in Lisp, that could explain the profiling differences.


    Oliver
-- 
13 Fructidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

Re: make-hash-table :size

[Oliver Scholz]

Oliver Scholz <alkibiades@gmx.de> writes:
[...]
> I assume that you use some extended CL compatibility package other
> than the one that comes with stock Emacs?  If that one overwrites
> Emacs' `assoc' (which is implemented in C) with a function implemented
> in Lisp, that could explain the profiling differences.
[...]

Indeed:  Using actual calls to cl.el's `assoc*' for comparision:

Function Name      Call Count  Elapsed Time  Average Time
=================  ==========  ============  ============
test-cl-assoc      10000       0.3100000000  3.10...e-005
test-alist-access  10000       0.09          9e-006
test-hash-access   10000       0.05          5e-006




(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 (table test key)
  (gethash key table))

(defun test-alist-access (table test key)
  (cdr (assq key table)))

(defun test-cl-assoc (table test key)
  ;; Passing the test here as an argument is necessary in order to
  ;; prevent `assoc*' being replaced via a compiler macro.
  (cdr (assoc* key table :test test)))

(dolist (f '(test-hash-access
	     test-alist-access
	     test-cl-assoc))
  (byte-compile f))

(elp-instrument-list  '(test-hash-access
			test-alist-access
			test-cl-assoc))

(defun test-run ()
  (interactive)
  (dotimes (ignore-me 10000)
    (test-hash-access test-hash 'eq 'alpha)
    (test-alist-access test-alist 'eq 'alpha)
    (test-cl-assoc test-alist 'eq 'alpha))
  (elp-results))



    Oliver
-- 
13 Fructidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

Re: make-hash-table :size

[Oliver Scholz]

Oliver Scholz <alkibiades@gmx.de> writes:

> Oliver Scholz <alkibiades@gmx.de> writes:
> [...]
>> I assume that you use some extended CL compatibility package other
>> than the one that comes with stock Emacs?  If that one overwrites
>> Emacs' `assoc' (which is implemented in C) with a function implemented
>> in Lisp, that could explain the profiling differences.
> [...]
>
> Indeed:  Using actual calls to cl.el's `assoc*' for comparision:
>
> Function Name      Call Count  Elapsed Time  Average Time
> =================  ==========  ============  ============
> test-cl-assoc      10000       0.3100000000  3.10...e-005
> test-alist-access  10000       0.09          9e-006
> test-hash-access   10000       0.05          5e-006

Hmph. Well, you have to take elp's results with a grain of salt ...

Function Name      Call Count  Elapsed Time  Average Time
=================  ==========  ============  ============
test-cl-assoc      10000       0.16          1.6e-005
test-alist-access  10000       0.02          2e-006
test-hash-access   10000       0.01          1e-006

Function Name      Call Count  Elapsed Time  Average Time
=================  ==========  ============  ============
test-cl-assoc      10000       0.1800000000  1.8e-005
test-hash-access   10000       0.02          2e-006
test-alist-access  10000       0.02          2e-006

Function Name      Call Count  Elapsed Time  Average Time
=================  ==========  ============  ============
test-cl-assoc      10000       0.1810000000  1.81...e-005
test-hash-access   10000       0.01          1e-006
test-alist-access  10000       0.0           0.0

Function Name      Call Count  Elapsed Time  Average Time
=================  ==========  ============  ============
test-cl-assoc      10000       0.2100000000  2.10...e-005
test-hash-access   10000       0.03          3e-006
test-alist-access  10000       0.02          2e-006


    Oliver
-- 
13 Fructidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

Re: make-hash-table :size

[Pascal Bourguignon]

Oliver Scholz <alkibiades@gmx.de> writes:
> > [...]
> >> I assume that you use some extended CL compatibility package other
> >> than the one that comes with stock Emacs?  If that one overwrites
> >> Emacs' `assoc' (which is implemented in C) with a function implemented
> >> in Lisp, that could explain the profiling differences.

Indeed, I've advised assoc. and call assq or ad-do-it only when
parameters match the usage.

> Hmph. Well, you have to take elp's results with a grain of salt ...
> 
> Function Name      Call Count  Elapsed Time  Average Time
> =================  ==========  ============  ============
> test-cl-assoc      10000       0.16          1.6e-005
> test-alist-access  10000       0.02          2e-006
> test-hash-access   10000       0.01          1e-006
 

-- 
__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.