performance of converting alist to hash table

performance of converting alist to hash table

[Dai Yuwen]

Dear all,

I'm trying to convert a large alist(nearly 7000 elements in it) to a
hash table. But I found the performence of my function is poor: on a
Celeron 333MHz, 196M memory system, it'll take 15 seconds to finish
converting. 

This is the function:

(defun convert-alist-to-hash (table  w)
  (let ((l w))
     (while l
       (setq char (car (car l))
             key (car (cdr (car l)))
             l (cdr l))
       (puthash char key table))))

And how I call the function:

(convert-alist-to-hash ta 
'(("w1" "aaaa")
("w2" "aa")
("w3" "aak")
...))

I once tried to write the above function as a macro since the alist is
known at compiling time so that most work will be done at compiling
time instead of runing time, but failed. Any idea? Thanks in advance.

Best regards,
Dai Yuwen

-- 
daiyuwen@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org

Re: performance of converting alist to hash table

[Thien-Thi Nguyen]

Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:

   Any idea?

what portion of the time is related to the hashing?

thi

Re: performance of converting alist to hash table

[Eli Zaretskii]

> Date: Sun, 16 May 2004 09:55:22 +0000
> From: Dai Yuwen <daiyuwen@sdf.lonestar.org>
> 
> I'm trying to convert a large alist(nearly 7000 elements in it) to a
> hash table. But I found the performence of my function is poor: on a
> Celeron 333MHz, 196M memory system, it'll take 15 seconds to finish
> converting. 
> 
> This is the function:
> 
> (defun convert-alist-to-hash (table  w)
>   (let ((l w))
>      (while l
>        (setq char (car (car l))
>              key (car (cdr (car l)))
>              l (cdr l))
>        (puthash char key table))))

Did you try `mapcar' and its variants?

Re: performance of converting alist to hash table

[Dai Yuwen]

On Sun, May 16, 2004 at 01:18:07PM +0200, Eli Zaretskii wrote:
> > Date: Sun, 16 May 2004 09:55:22 +0000
> > From: Dai Yuwen <daiyuwen@sdf.lonestar.org>
> > 
> > I'm trying to convert a large alist(nearly 7000 elements in it) to a
> > hash table. But I found the performence of my function is poor: on a
> > Celeron 333MHz, 196M memory system, it'll take 15 seconds to finish
> > converting. 
> > 
> > This is the function:
> > 
> > (defun convert-alist-to-hash (table  w)
> >   (let ((l w))
> >      (while l
> >        (setq char (car (car l))
> >              key (car (cdr (car l)))
> >              l (cdr l))
> >        (puthash char key table))))
> 
> Did you try `mapcar' and its variants?
> 
I use `mapc' like this:
(defun convert-alist-to-hash (table  w)
  (mapc (lambda (e)
          (puthash (car e) (cadr e) table))
        w))

Almost the same time needed. (I made a mistake in the previous email, it should be 30 seconds instead of 15.) 

best regards,
Dai Yuwen

-- 
daiyuwen@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org

Re: performance of converting alist to hash table

[Dai Yuwen]

On Sun, May 16, 2004 at 06:13:33AM -0400, Thien-Thi Nguyen wrote:
> Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:
> 
>    Any idea?
> 
> what portion of the time is related to the hashing?
I don't know. I just profiled the function, elp-results:
Function Name          Call Count  Elapsed Time  Average Time
=====================  ==========  ============  ============
convert-alist-to-hash  1           24.243946     24.243946

Best regards,
Dai Yuwen
> 
> thi

-- 
daiyuwen@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org

Re: performance of converting alist to hash table

[Andreas Schwab]

Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:

> I use `mapc' like this:
> (defun convert-alist-to-hash (table  w)
>   (mapc (lambda (e)
>           (puthash (car e) (cadr e) table))
>         w))
>
> Almost the same time needed. (I made a mistake in the previous email, it should be 30 seconds instead of 15.) 

How did you create the hash table?  You should probably start with a
larger hash table than the default to avoid too many resize operations.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: performance of converting alist to hash table

[Adrian Aichner]

[-- Attachment #1: Type: text/plain, Size: 658 bytes --]

Andreas Schwab <schwab@suse.de> writes:

> Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:
>
>> I use `mapc' like this:
>> (defun convert-alist-to-hash (table  w)
>>   (mapc (lambda (e)
>>           (puthash (car e) (cadr e) table))
>>         w))
>>
>> Almost the same time needed. (I made a mistake in the previous email, it should be 30 seconds instead of 15.) 
>
> How did you create the hash table?  You should probably start with a
> larger hash table than the default to avoid too many resize operations.
>
> Andreas.

Here's what I get for
M-x profile-sexp RET (convert-alist-to-hash (make-hash-table :size 70000) a-list)

based on these definitions:


[-- Attachment #2: convert-alist-to-hash.el --]
[-- Type: application/emacs-lisp, Size: 409 bytes --]

[-- Attachment #3: Type: text/plain, Size: 48 bytes --]


Profiling results on a Dell C600 with 850MHz:


[-- Attachment #4: Type: text/plain, Size: 1917 bytes --]

Function Name             Ticks/Total %Usage Calls GC-Usage/  Total
===============================/===== ====== ===== ========/=======
(profile overhead)          345/  345 59.689                       
setq                        101/  380 17.474 70000                 
while                        82/  571 14.187     1       56/     56
make-hash-table              27/   27  4.671     1       64/     64
puthash                      10/   10  1.730 70000                 
cdr                           8/    8  1.384 140000                 
car                           5/    7  0.865 280000                 
unwind-protect                0/  598  0.000              0/    108
convert-alist-to-hash         0/  571  0.000     1        0/     56
profile-sexp                  0/  598  0.000              0/    108
with-output-to-temp-buffer    0/  598  0.000              0/    108
progn                         0/  598  0.000              0/    108
stop-profiling                0/    0  0.000     1                 
let                           0/  598  0.000     1        0/    108
command-execute               0/  598  0.000              0/    108
call-interactively            0/  598  0.000              0/    108
start-profiling               0/    0  0.000            -12/    -12
profile                       0/  598  0.000              0/    108
eval                          0/  598  0.000     1        0/    120
profile-results               0/  598  0.000              0/    108
execute-extended-command      0/  598  0.000              0/    108
-------------------------------------------------------------------
Total                       578      100.000 560006      108


Ticks/Total     = Ticks this function/this function and descendants
Calls           = Number of calls to this function
GC-Usage/Total  = Lisp allocation this function/this function and descendants
One tick        = 1 ms

[-- Attachment #5: Type: text/plain, Size: 70 bytes --]


-- 
Adrian Aichner
 mailto:adrian@xemacs.org
 http://www.xemacs.org/

[-- Attachment #6: Type: text/plain, Size: 141 bytes --]

_______________________________________________
Emacs-devel mailing list
Emacs-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/emacs-devel

Re: performance of converting alist to hash table

[Dai Yuwen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=unknown-8bit, Size: 1052 bytes --]

On Sun, May 16, 2004 at 04:02:00PM +0200, Andreas Schwab wrote:
> Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:
> 
> > I use `mapc' like this:
> > (defun convert-alist-to-hash (table  w)
> >   (mapc (lambda (e)
> >           (puthash (car e) (cadr e) table))
> >         w))
> >
> > Almost the same time needed. (I made a mistake in the previous email, it should be 30 seconds instead of 15.) 
> 
> How did you create the hash table?  You should probably start with a
> larger hash table than the default to avoid too many resize operations.
> 
I realized this. I created the hash table like this:
(setq ta (make-hash-table :test 'equal :size 7000))

and the actuaal length of the alist is 6727.

> Andreas.
> 
> -- 
> Andreas Schwab, SuSE Labs, schwab@suse.de
> SuSE Linux AG, Maxfeldstraße 5, 90409 Nürnberg, Germany
> Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
> "And now for something completely different."

-- 
daiyuwen@freeshell.org
SDF Public Access UNIX System - http://sdf.lonestar.org

Re: performance of converting alist to hash table

[Ted Zlatanov]

On Sun, 16 May 2004, daiyuwen@sdf.lonestar.org wrote:

> I'm trying to convert a large alist(nearly 7000 elements in it) to a
> hash table. But I found the performence of my function is poor: on a
> Celeron 333MHz, 196M memory system, it'll take 15 seconds to finish
> converting. 

I use this function in the Gnus gnus-registry.el code:

(defun alist-to-hashtable (alist)
  "Build a hashtable from the values in ALIST."
  (let ((ht (make-hash-table 			    
	     :size 4096
	     :test 'equal)))
    (mapc
     (lambda (kv-pair)
       (puthash (car kv-pair) (cdr kv-pair) ht))
     alist)
     ht))

It loads my 5000-entry registry alist quickly even on a relatively
slow (UltraSPARC-IIe 650 MHz) processor.  Is it slow for you?  Maybe
the equality test you are using is too slow?

Ted

Re: performance of converting alist to hash table

[Miles Bader]

On Mon, May 17, 2004 at 01:43:41PM -0400, Ted Zlatanov wrote:
> Maybe the equality test you are using is too slow?

I think that's a good point -- specifying _any_ non-standard :test function
(that is, anything except eq/eql/equal) probably slows down hashing quite a
bit.

-Miles
-- 
Any man who is a triangle, has thee right, when in Cartesian Space, to
have angles, which when summed, come to know more, nor no less, than
nine score degrees, should he so wish.  [TEMPLE OV THEE LEMUR]

Re: performance of converting alist to hash table

[Dai Yuwen]

On Mon, May 17, 2004 at 07:37:43PM -0400, Miles Bader wrote:
> On Mon, May 17, 2004 at 01:43:41PM -0400, Ted Zlatanov wrote:
> > Maybe the equality test you are using is too slow?
> 
> I think that's a good point -- specifying _any_ non-standard :test function
> (that is, anything except eq/eql/equal) probably slows down hashing quite a
> bit.
> 
I use equal as the test function:
(setq ta (make-hash-table :test 'equal :size 7000))

But I forgot to mention: the key of hash is a Chinese GB2312 string. Does this slow down hashing?

I decide to give up using hash. After all alist behaves like hash. All I need is a function like gethash:
(defun get-value (key)
   (cadr (assoc key alist)))

I profiled get-value and gethash, the result is acceptable, though get-value is slower.

Best regards,
Dai Yuwen

Re: performance of converting alist to hash table

[David Kastrup]

Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:

> Dear all,
> 
> I'm trying to convert a large alist(nearly 7000 elements in it) to a
> hash table. But I found the performence of my function is poor: on a
> Celeron 333MHz, 196M memory system, it'll take 15 seconds to finish
> converting. 
> 
> This is the function:
> 
> (defun convert-alist-to-hash (table  w)
>   (let ((l w))
>      (while l
>        (setq char (car (car l))
>              key (car (cdr (car l)))
>              l (cdr l))
>        (puthash char key table))))
> 
> And how I call the function:
> 
> (convert-alist-to-hash ta 
> '(("w1" "aaaa")
> ("w2" "aa")
> ("w3" "aak")
> ...))

Did you byte-compile the function?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: performance of converting alist to hash table

[Stefan Monnier]

> I use equal as the test function:
> (setq ta (make-hash-table :test 'equal :size 7000))

> But I forgot to mention: the key of hash is a Chinese GB2312
> string. Does this slow down hashing?

Can you post your complete code so we can reproduce the problem?


        Stefan

Re: performance of converting alist to hash table

[Dai Yuwen]

[-- Attachment #1: Type: text/plain, Size: 427 bytes --]

On Tue, May 18, 2004 at 09:42:20AM -0400, Stefan Monnier wrote:
> > I use equal as the test function:
> > (setq ta (make-hash-table :test 'equal :size 7000))
> 
> > But I forgot to mention: the key of hash is a Chinese GB2312
> > string. Does this slow down hashing?
> 
> Can you post your complete code so we can reproduce the problem?
> 
> 
I attach the el file in the mail. There're GB2312 strings in the alist.

Dai Yuwen


[-- Attachment #2: ex3.el.gz --]
[-- Type: application/x-gunzip, Size: 32203 bytes --]

[-- Attachment #3: Type: text/plain, Size: 141 bytes --]

_______________________________________________
Emacs-devel mailing list
Emacs-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/emacs-devel

Re: performance of converting alist to hash table

[Dai Yuwen]

On Tue, May 18, 2004 at 02:23:46PM +0200, David Kastrup wrote:
> Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:
> 
> > Dear all,
> > 
> > I'm trying to convert a large alist(nearly 7000 elements in it) to a
> > hash table. But I found the performence of my function is poor: on a
> > Celeron 333MHz, 196M memory system, it'll take 15 seconds to finish
> > converting. 
> > 
> > This is the function:
> > 
> > (defun convert-alist-to-hash (table  w)
> >   (let ((l w))
> >      (while l
> >        (setq char (car (car l))
> >              key (car (cdr (car l)))
> >              l (cdr l))
> >        (puthash char key table))))
> > 
> > And how I call the function:
> > 
> > (convert-alist-to-hash ta 
> > '(("w1" "aaaa")
> > ("w2" "aa")
> > ("w3" "aak")
> > ...))
> 
> Did you byte-compile the function?
No matter whether I compiled the function or not, the result almost the same.

> 
-- 
daiyuwen@freeshell.org
SDF Public Access UNIX System - http://sdf.lonestar.org

Re: performance of converting alist to hash table

[Kenichi Handa]

In article <20040519115903.GA2149@SDF.LONESTAR.ORG>, Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:

> [1  <text/plain; us-ascii (7bit)>]
> On Tue, May 18, 2004 at 09:42:20AM -0400, Stefan Monnier wrote:
>>  > I use equal as the test function:
>>  > (setq ta (make-hash-table :test 'equal :size 7000))
>>  
>>  > But I forgot to mention: the key of hash is a Chinese GB2312
>>  > string. Does this slow down hashing?
>>  
>>  Can you post your complete code so we can reproduce the problem?
>>  
>>  
> I attach the el file in the mail. There're GB2312 strings in the alist.

As keys are all one-char strings, I think a char-table is
the most efficient method.

(put 'wubi-table 'char-table-extra-slots 0)
(defvar wubi-table (make-char-table 'wubi-table nil))

(defun convert-alist-to-char-table (table w)
  (mapc #'(lambda (e)
	    (aset table (aref (car e) 0) (cadr e)))
	w))

;;;; WuBi code for single Chinese char
(convert-alist-to-char-table wubi-table '(
[...]

You can access the value by (aref wubi-table
?_CHINESE_CHAR_), which is also very fast compared to
gethash and assq.

If you also want a reverse mapping (i.e. WuBi to chinese
char), you can use nested-alist.

---
Ken'ichi HANDA
handa@m17n.org

Re: performance of converting alist to hash table

[Dai Yuwen]

On Thu, May 20, 2004 at 08:27:30AM +0900, Kenichi Handa wrote:
> In article <20040519115903.GA2149@SDF.LONESTAR.ORG>, Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:
> 
> > [1  <text/plain; us-ascii (7bit)>]
> > On Tue, May 18, 2004 at 09:42:20AM -0400, Stefan Monnier wrote:
> >>  > I use equal as the test function:
> >>  > (setq ta (make-hash-table :test 'equal :size 7000))
> >>  
> >>  > But I forgot to mention: the key of hash is a Chinese GB2312
> >>  > string. Does this slow down hashing?
> >>  
> >>  Can you post your complete code so we can reproduce the problem?
> >>  
> >>  
> > I attach the el file in the mail. There're GB2312 strings in the alist.
> 
> As keys are all one-char strings, I think a char-table is
> the most efficient method.
> 
> (put 'wubi-table 'char-table-extra-slots 0)
> (defvar wubi-table (make-char-table 'wubi-table nil))
> 
> (defun convert-alist-to-char-table (table w)
>   (mapc #'(lambda (e)
> 	    (aset table (aref (car e) 0) (cadr e)))
> 	w))
> 
> ;;;; WuBi code for single Chinese char
> (convert-alist-to-char-table wubi-table '(
> [...]
> 
> You can access the value by (aref wubi-table
> ?_CHINESE_CHAR_), which is also very fast compared to
> gethash and assq.
> 
> If you also want a reverse mapping (i.e. WuBi to chinese
> char), you can use nested-alist.
> 
Thank you very much. I tried convert-alist-to-char-table. It runs suprisingly fast,
and (aref wubi-talbe ?_CHINESE_CHAR_) also runs much faster than gethash and
(cadr (assoc alist key)).

By the way, how do you know I'm writing a Wubi input method? Do you familiar with it?

best regards,
Dai yuwen
 
> ---
> Ken'ichi HANDA
> handa@m17n.org

-- 
daiyuwen@freeshell.org
SDF Public Access UNIX System - http://sdf.lonestar.org

Re: performance of converting alist to hash table

[Kenichi Handa]

In article <20040526132936.GA22985@SDF.LONESTAR.ORG>, Dai Yuwen <daiyuwen@sdf.lonestar.org> writes:

> Thank you very much. I tried
> convert-alist-to-char-table. It runs suprisingly fast, and
> (aref wubi-talbe ?_CHINESE_CHAR_) also runs much faster
> than gethash and (cadr (assoc alist key)).

> By the way, how do you know I'm writing a Wubi input
> method? Do you familiar with it?

No, I'm not familiar with it, but you wrote "WuBi" in the
file ex3.el that you sent.

---
Ken'ichi HANDA
handa@m17n.org