* Re: new function proposal alist-to-hash @ 2019-10-04 9:58 Andrea Corallo 2019-10-04 19:16 ` Stefan Monnier 0 siblings, 1 reply; 20+ messages in thread From: Andrea Corallo @ 2019-10-04 9:58 UTC (permalink / raw) To: akrl; +Cc: Stefan Monnier, emacs-devel I just wanted elaborate a little more on the following two points: - I think is quite useful to be able to create in a concise and explicit way nested hash tables. This is a common feature of many "modern" languages. Here both solutions compared: (alist-to-hash '((a . x) (b . ((i . j) (k . l))) (c . y))) (map-into `((a . x) (b . ,(map-into '((i . j) (k . l)) 'hash-table)) (c . y)) 'hash-table) - map-into does not let you tweak make-hash-table parameters. This is especially a limitation regarding :test so is effectively a solution to say ~50% of the use cases. Bests Andrea -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: new function proposal alist-to-hash 2019-10-04 9:58 new function proposal alist-to-hash Andrea Corallo @ 2019-10-04 19:16 ` Stefan Monnier 2019-10-05 8:18 ` Andrea Corallo 2019-10-05 8:28 ` [PATCH] extend map-into (was: new function proposal alist-to-hash) Andrea Corallo 0 siblings, 2 replies; 20+ messages in thread From: Stefan Monnier @ 2019-10-04 19:16 UTC (permalink / raw) To: Andrea Corallo; +Cc: emacs-devel > - I think is quite useful to be able to create in a concise and > explicit way nested hash tables. This is a common feature of many > "modern" languages. > Here both solutions compared: > > (alist-to-hash '((a . x) > (b . ((i . j) > (k . l))) > (c . y))) > > (map-into `((a . x) > (b . ,(map-into '((i . j) > (k . l)) > 'hash-table)) > (c . y)) > 'hash-table) Not sure I understand: if you only use it for immediate/literal data, then I guess you could just use the #s(hash-table data (...)) syntax. And for non-literal maps, this needs to somehow distinguish values that are alists from others, like (map-into (mapcar (lambda (x) (if (and (consp (cdr x)) (consp (cadr x))) (cons (car x) (map-into (cdr x) 'hash-table)) x)) my-alist) 'hash-table) But I suspect that this is not frequently needed. [ BTW, the above code is screaming for something like `map-values-apply` but which returns a *map* rather than a list. ] And if you really need this to apply recursively, it basically means you don't have a map but a *tree* where each node is originally implemented as an alist and which you want to transform into the same tree where each node is now a hash-table. Again, this is likely not needed very frequently (and I suspect that each time it's needed, it will have slightly different needs/constraints). > - map-into does not let you tweak make-hash-table parameters. > This is especially a limitation regarding :test so is effectively a > solution to say ~50% of the use cases. Yes, this is a very serious limitation of `map-into`. I decided not to try to tackle it when I converted map.el to use cl-defmethod, but I'd welcome help on this. Stefan ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: new function proposal alist-to-hash 2019-10-04 19:16 ` Stefan Monnier @ 2019-10-05 8:18 ` Andrea Corallo 2019-10-05 15:13 ` Stefan Monnier 2019-10-05 8:28 ` [PATCH] extend map-into (was: new function proposal alist-to-hash) Andrea Corallo 1 sibling, 1 reply; 20+ messages in thread From: Andrea Corallo @ 2019-10-05 8:18 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-devel Stefan Monnier <monnier@iro.umontreal.ca> writes: >> - I think is quite useful to be able to create in a concise and >> explicit way nested hash tables. This is a common feature of many >> "modern" languages. >> Here both solutions compared: >> >> (alist-to-hash '((a . x) >> (b . ((i . j) >> (k . l))) >> (c . y))) >> >> (map-into `((a . x) >> (b . ,(map-into '((i . j) >> (k . l)) >> 'hash-table)) >> (c . y)) >> 'hash-table) > > Not sure I understand: if you only use it for immediate/literal data, > then I guess you could just use the #s(hash-table data (...)) syntax. Sure, my example was just to point out easiness of use from a syntactic point of view. The good of having the list quoted by the user is that he can quasi-quote when needed what he needs. > And for non-literal maps, this needs to somehow distinguish values that > are alists from others, like > > (map-into (mapcar (lambda (x) > (if (and (consp (cdr x)) (consp (cadr x))) > (cons (car x) (map-into (cdr x) 'hash-table)) > x)) > my-alist) > 'hash-table) > > But I suspect that this is not frequently needed. > [ BTW, the above code is screaming for something like `map-values-apply` > but which returns a *map* rather than a list. ] > > And if you really need this to apply recursively, it basically means > you don't have a map but a *tree* where each node is originally > implemented as an alist and which you want to transform into the same > tree where each node is now a hash-table. Again, this is likely not > needed very frequently (and I suspect that each time it's needed, it > will have slightly different needs/constraints). I've maybe used not the correct nomenclature sorry. What I want to say is that being an hash table a key value map it maps 1:1 into alist. That said I think is quite important to be able to express in a clear and short way nested hashes. In python it would be simply something like this: nested_dict = { 'dictA': {'key_1': 'value_1'}, 'dictB': {'key_2': 'value_2'}} Note that here just litteral are used but also variables can be evaluated while creating the dictionaries. A tree of a-list for the reason I've expressed above would be to me the most natural way to express the same. Given that a recursive implementation that walks this tree like the one in patch I've posted can do the job. Maybe I'm the only that see a value on that but I think is useful :) >> - map-into does not let you tweak make-hash-table parameters. >> This is especially a limitation regarding :test so is effectively a >> solution to say ~50% of the use cases. > > Yes, this is a very serious limitation of `map-into`. > I decided not to try to tackle it when I converted map.el to use > cl-defmethod, but I'd welcome help on this. > > > Stefan Ok I'm looking into it. Bests Andrea -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: new function proposal alist-to-hash 2019-10-05 8:18 ` Andrea Corallo @ 2019-10-05 15:13 ` Stefan Monnier 2019-10-05 15:45 ` Andrea Corallo 0 siblings, 1 reply; 20+ messages in thread From: Stefan Monnier @ 2019-10-05 15:13 UTC (permalink / raw) To: Andrea Corallo; +Cc: emacs-devel > Sure, my example was just to point out easiness of use from a syntactic > point of view. The good of having the list quoted by the user is that > he can quasi-quote when needed what he needs. But reading the rest of your response, it seems you're mostly interested in the "literal" case (maybe using backquote+unquote to evaluate some sub-elements). > In python it would be simply something like this: > > nested_dict = { 'dictA': {'key_1': 'value_1'}, > 'dictB': {'key_2': 'value_2'}} Python uses hash-tables to represent objects, whereas in Elisp this is not the case: we use cl-defstruct, alist, or plists instead (hash-tables are considered as relatively expensive, so if you know there will only be a small number of entries, you're often better off with an alist). Nested hash-tables are very rare in Elisp (so far). Stefan ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: new function proposal alist-to-hash 2019-10-05 15:13 ` Stefan Monnier @ 2019-10-05 15:45 ` Andrea Corallo 0 siblings, 0 replies; 20+ messages in thread From: Andrea Corallo @ 2019-10-05 15:45 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-devel Stefan Monnier <monnier@iro.umontreal.ca> writes: >> Sure, my example was just to point out easiness of use from a syntactic >> point of view. The good of having the list quoted by the user is that >> he can quasi-quote when needed what he needs. > > But reading the rest of your response, it seems you're mostly interested > in the "literal" case (maybe using backquote+unquote to evaluate some > sub-elements). Correct. >> In python it would be simply something like this: >> >> nested_dict = { 'dictA': {'key_1': 'value_1'}, >> 'dictB': {'key_2': 'value_2'}} > > Python uses hash-tables to represent objects, whereas in Elisp this is > not the case: we use cl-defstruct, alist, or plists instead (hash-tables > are considered as relatively expensive, so if you know there will only > be a small number of entries, you're often better off with an alist). > > Nested hash-tables are very rare in Elisp (so far). I guess one of the reasons is that as discussed depending on the case expressing them in a literal form can be not so convenient. > Stefan > Bests Andrea -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH] extend map-into (was: new function proposal alist-to-hash) 2019-10-04 19:16 ` Stefan Monnier 2019-10-05 8:18 ` Andrea Corallo @ 2019-10-05 8:28 ` Andrea Corallo 2019-10-06 14:02 ` [PATCH] extend map-into Stefan Monnier 1 sibling, 1 reply; 20+ messages in thread From: Andrea Corallo @ 2019-10-05 8:28 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 405 bytes --] Stefan Monnier <monnier@iro.umontreal.ca> writes: > Yes, this is a very serious limitation of `map-into`. > I decided not to try to tackle it when I converted map.el to use > cl-defmethod, but I'd welcome help on this. > > > Stefan Hi, would a solution like the one in attached patch do the job? I've added a rest arg so that the current code should not be impacted. Andrea -- akrl@sdf.org [-- Attachment #2: 0001-Extend-map-into-for-better-control-on-hash-table-cre.patch --] [-- Type: text/x-patch, Size: 2950 bytes --] From 2b94c00384f7bd4bfd7b6108e5be3b261e1cf018 Mon Sep 17 00:00:00 2001 From: Andrea Corallo <akrl@sdf.org> Date: Sat, 5 Oct 2019 09:38:13 +0200 Subject: [PATCH] Extend 'map-into' for better control on hash table creation --- etc/NEWS | 5 +++++ lisp/emacs-lisp/map.el | 22 ++++++++++++---------- 2 files changed, 17 insertions(+), 10 deletions(-) diff --git a/etc/NEWS b/etc/NEWS index c8cc753..caea917 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -24,6 +24,11 @@ applies, and please also update docstrings as needed. \f * Installation Changes in Emacs 27.1 +** Extend function 'map-into'. +Change 'map-into' lambda-list into (map type &rest args). +When 'map-into' is used to create hash tables args are now forwarded to +'make-hash-table' for better control. + ** Emacs now uses GMP, the GNU Multiple Precision library. By default, if 'configure' does not find a suitable libgmp, it arranges for the included mini-gmp library to be built and used. diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el index 54e802e..7360705 100644 --- a/lisp/emacs-lisp/map.el +++ b/lisp/emacs-lisp/map.el @@ -367,12 +367,12 @@ map-merge-with (pop maps))) result)) -(cl-defgeneric map-into (map type) +(cl-defgeneric map-into (map type &rest args) "Convert the map MAP into a map of type TYPE.") ;; FIXME: I wish there was a way to avoid this η-redex! -(cl-defmethod map-into (map (_type (eql list))) (map-pairs map)) -(cl-defmethod map-into (map (_type (eql alist))) (map-pairs map)) -(cl-defmethod map-into (map (_type (eql plist))) +(cl-defmethod map-into (map (_type (eql list)) &rest _) (map-pairs map)) +(cl-defmethod map-into (map (_type (eql alist)) &rest _) (map-pairs map)) +(cl-defmethod map-into (map (_type (eql plist)) &rest _) (let ((plist '())) (map-do (lambda (k v) (setq plist `(,k ,v ,@plist))) map) plist)) @@ -458,12 +458,14 @@ map-do (funcall function index elt)) array)) -(cl-defmethod map-into (map (_type (eql hash-table))) - "Convert MAP into a hash-table." - ;; FIXME: Just knowing we want a hash-table is insufficient, since that - ;; doesn't tell us the test function to use with it! - (let ((ht (make-hash-table :size (map-length map) - :test 'equal))) +(cl-defmethod map-into (map (_type (eql hash-table)) &rest keyword-args) + "Convert MAP into a hash-table. +If KEYWORD-ARGS are provided they are forwarded to `make-hash-table'. +If KEYWORD-ARGS is nil hash table size is set to MAP length and test to `equal'." + (let* ((h-args (if keyword-args + keyword-args + (list :size (map-length map) :test 'equal))) + (ht (apply #'make-hash-table h-args))) (map-apply (lambda (key value) (setf (map-elt ht key) value)) map) -- 2.7.4 ^ permalink raw reply related [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-05 8:28 ` [PATCH] extend map-into (was: new function proposal alist-to-hash) Andrea Corallo @ 2019-10-06 14:02 ` Stefan Monnier 2019-10-06 20:59 ` Andrea Corallo 0 siblings, 1 reply; 20+ messages in thread From: Stefan Monnier @ 2019-10-06 14:02 UTC (permalink / raw) To: Andrea Corallo; +Cc: Nicolas Petton, emacs-devel [ I added Nicolas explicitly in the list, in case he's too busy to read all messages. ] > would a solution like the one in attached patch do the job? Yes and no: it does the job, but only for `map-into`. So that doesn't immediately cover the needs of `map-merge` and other callers of `map-into` (e.g. the `map-values-apply` I suggested which would return a new map). I guess we could use a `type` that's not a symbol but a list (whose head is a symbol and the rest are the args), but it could be a bit inconvenient (and would impact efficiency as well because it makes the cl-generic dispatch more complex). On a related note, maybe it would be good to have map.el primitives that let you create a new map of the same type as another (preserving :test). > + (let* ((h-args (if keyword-args > + keyword-args > + (list :size (map-length map) :test 'equal))) Aka (or keyword-args (list :size (map-length map) :test 'equal)) Stefan ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-06 14:02 ` [PATCH] extend map-into Stefan Monnier @ 2019-10-06 20:59 ` Andrea Corallo 2019-10-08 17:29 ` Stefan Monnier 0 siblings, 1 reply; 20+ messages in thread From: Andrea Corallo @ 2019-10-06 20:59 UTC (permalink / raw) To: Stefan Monnier; +Cc: Nicolas Petton, emacs-devel [-- Attachment #1: Type: text/plain, Size: 1174 bytes --] Stefan Monnier <monnier@iro.umontreal.ca> writes: > [ I added Nicolas explicitly in the list, in case he's too busy to read > all messages. ] > >> would a solution like the one in attached patch do the job? > > Yes and no: it does the job, but only for `map-into`. So that doesn't > immediately cover the needs of `map-merge` and other callers of > `map-into` (e.g. the `map-values-apply` I suggested which would return > a new map). > > I guess we could use a `type` that's not a symbol but a list (whose > head is a symbol and the rest are the args), but it could be a bit > inconvenient (and would impact efficiency as well because it makes the > cl-generic dispatch more complex). Cool, is the attached patch doing what you suggest? > On a related note, maybe it would be good to have map.el primitives that > let you create a new map of the same type as another (preserving :test). > >> + (let* ((h-args (if keyword-args >> + keyword-args >> + (list :size (map-length map) :test 'equal))) > > Aka (or keyword-args (list :size (map-length map) :test 'equal)) > ops :D > Stefan > Bests Andrea -- akrl@sdf.org [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #2: 0001-Extend-map-into-for-better-control-on-hash-table-cre.patch --] [-- Type: text/x-patch, Size: 3224 bytes --] From 55780be0af0e8443fb9b14b77cb3d13ca9af75fb Mon Sep 17 00:00:00 2001 From: Andrea Corallo <akrl@sdf.org> Date: Sun, 6 Oct 2019 22:43:11 +0200 Subject: [PATCH] Extend 'map-into' for better control on hash table creation. --- etc/NEWS | 4 ++++ lisp/emacs-lisp/map.el | 29 +++++++++++++++++++++-------- 2 files changed, 25 insertions(+), 8 deletions(-) diff --git a/etc/NEWS b/etc/NEWS index c8cc753..5942a32 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -24,6 +24,10 @@ applies, and please also update docstrings as needed. \f * Installation Changes in Emacs 27.1 +** Extend function 'map-into'. +Add a 'map-into' method to have hash table creation parameters +tweak-able. + ** Emacs now uses GMP, the GNU Multiple Precision library. By default, if 'configure' does not find a suitable libgmp, it arranges for the included mini-gmp library to be built and used. diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el index 54e802e..dfc1500 100644 --- a/lisp/emacs-lisp/map.el +++ b/lisp/emacs-lisp/map.el @@ -338,7 +338,8 @@ map-every-p t)) (defun map-merge (type &rest maps) - "Merge into a map of type TYPE all the key/value pairs in MAPS." + "Merge into a map of type TYPE all the key/value pairs in MAPS. +See `map-into' for all supported values of TYPE." (let ((result (map-into (pop maps) type))) (while maps ;; FIXME: When `type' is `list', we get an O(N^2) behavior. @@ -354,7 +355,8 @@ map-merge-with "Merge into a map of type TYPE all the key/value pairs in MAPS. When two maps contain the same key (`eql'), call FUNCTION on the two values and use the value returned by it. -MAP can be a list, hash-table or array." +MAP can be a list, hash-table or array. +See `map-into' for all supported values of TYPE." (let ((result (map-into (pop maps) type)) (not-found (cons nil nil))) (while maps @@ -458,17 +460,28 @@ map-do (funcall function index elt)) array)) -(cl-defmethod map-into (map (_type (eql hash-table))) - "Convert MAP into a hash-table." - ;; FIXME: Just knowing we want a hash-table is insufficient, since that - ;; doesn't tell us the test function to use with it! - (let ((ht (make-hash-table :size (map-length map) - :test 'equal))) +(defsubst map--into-hash (map keyword-args) + "Convert MAP into a hash-table. +KEYWORD-ARGS are forwarded to `make-hash-table'." + (let ((ht (apply #'make-hash-table keyword-args))) (map-apply (lambda (key value) (setf (map-elt ht key) value)) map) ht)) +(cl-defmethod map-into (map (_type (eql hash-table))) + "Convert MAP into a hash-table." + (map--into-hash map (list :size (map-length map) :test 'equal))) + +(cl-defmethod map-into (map (args (head hash-table))) + "Convert MAP into a hash-table. +ARGS is a list where the car is 'hash-table' and the cdr are the keyword-args + forwarded to `make-hash-table'. + +Example: + (map-into '((1 . 3)) '(hash-table :test eql))" + (map--into-hash map (cdr args))) + (defun map--make-pcase-bindings (args) "Return a list of pcase bindings from ARGS to the elements of a map." (seq-map (lambda (elt) -- 2.7.4 ^ permalink raw reply related [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-06 20:59 ` Andrea Corallo @ 2019-10-08 17:29 ` Stefan Monnier 2019-10-08 18:46 ` Andrea Corallo 0 siblings, 1 reply; 20+ messages in thread From: Stefan Monnier @ 2019-10-08 17:29 UTC (permalink / raw) To: Andrea Corallo, Nicolas Petton; +Cc: emacs-devel >> I guess we could use a `type` that's not a symbol but a list (whose >> head is a symbol and the rest are the args), but it could be a bit >> inconvenient (and would impact efficiency as well because it makes the >> cl-generic dispatch more complex). > Cool, is the attached patch doing what you suggest? Yes. Have you taken a look at the performance impact? E.g. how much slower does something like (map-into nil 'alist) becomes (this should be pretty the worst case which spends most/all its time in the dispatch)? Nicolas, WDYT? Stefan ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-08 17:29 ` Stefan Monnier @ 2019-10-08 18:46 ` Andrea Corallo 2019-10-08 20:23 ` Stefan Monnier 0 siblings, 1 reply; 20+ messages in thread From: Andrea Corallo @ 2019-10-08 18:46 UTC (permalink / raw) To: Stefan Monnier; +Cc: Nicolas Petton, emacs-devel Stefan Monnier <monnier@iro.umontreal.ca> writes: >>> I guess we could use a `type` that's not a symbol but a list (whose >>> head is a symbol and the rest are the args), but it could be a bit >>> inconvenient (and would impact efficiency as well because it makes the >>> cl-generic dispatch more complex). >> Cool, is the attached patch doing what you suggest? > > Yes. Have you taken a look at the performance impact? > E.g. how much slower does something like (map-into nil 'alist) becomes > (this should be pretty the worst case which spends most/all its time in > the dispatch)? I can tell you what I did just now and you tell me if it makes sense. I've created a function with as body an unrolled loop that calls 10000 times (map-into nil 'alist). Once byte compiled I've run it with the current map.el and then with the new one loaded. On my machine both versions runs in about the same time (~0.04-0.03 secs), if there's some difference for this simple test is just noise. Interesting, I would bet on funcall as responsible but I admit I don't know how the dynamic dispatch is implemented in details. > Nicolas, WDYT? > > > Stefan Bests Andrea -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-08 18:46 ` Andrea Corallo @ 2019-10-08 20:23 ` Stefan Monnier 2019-10-09 15:35 ` Andrea Corallo 0 siblings, 1 reply; 20+ messages in thread From: Stefan Monnier @ 2019-10-08 20:23 UTC (permalink / raw) To: Andrea Corallo; +Cc: Nicolas Petton, emacs-devel > I can tell you what I did just now and you tell me if it makes sense. > I've created a function with as body an unrolled loop that calls 10000 > times (map-into nil 'alist). > Once byte compiled I've run it with the current map.el and then with the > new one loaded. That sounds about right. Tho, you can also use something like `benchmark` for that. > On my machine both versions runs in about the same time (~0.04-0.03 > secs), if there's some difference for this simple test is just noise. 0.03 seconds is too small for a meaningful measure, in my experience, I recommend you add 2 zeroes to the number of iterations to bring it into the realm of "a few seconds". But, yes, there's a chance the difference is negligible (more time is spent in the funcall/apply machinery itself and/or the hash lookup than the specific computation of the "tag" used to index the hash-table, which is the part that depends on the set of specializers used on a particular argument of a generic function). Stefan ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-08 20:23 ` Stefan Monnier @ 2019-10-09 15:35 ` Andrea Corallo 2019-10-09 19:41 ` Stefan Monnier 0 siblings, 1 reply; 20+ messages in thread From: Andrea Corallo @ 2019-10-09 15:35 UTC (permalink / raw) To: Stefan Monnier; +Cc: Nicolas Petton, emacs-devel Stefan Monnier <monnier@iro.umontreal.ca> writes: >> I can tell you what I did just now and you tell me if it makes sense. >> I've created a function with as body an unrolled loop that calls 10000 >> times (map-into nil 'alist). >> Once byte compiled I've run it with the current map.el and then with the >> new one loaded. > > That sounds about right. Tho, you can also use something like > `benchmark` for that. > >> On my machine both versions runs in about the same time (~0.04-0.03 >> secs), if there's some difference for this simple test is just noise. > > 0.03 seconds is too small for a meaningful measure, in my experience, > I recommend you add 2 zeroes to the number of iterations to bring it > into the realm of "a few seconds". > > But, yes, there's a chance the difference is negligible (more time is > spent in the funcall/apply machinery itself and/or the hash lookup than > the specific computation of the "tag" used to index the hash-table, > which is the part that depends on the set of specializers used on > a particular argument of a generic function). > > > Stefan I've repeated the same test going up two magnitude orders (1000000 iterations). Still the execution time (~1.7secs) seems not distinguishable between the old and the implementation. For my curiosity I've also tried to run it using `benchmark-run-compiled' with a very similar execution time as result. I would have expected to have the unrolled version faster but apparently funcall is not the bottle-neck here. As usual when profiling guessing proves to be not a good idea. Bests Andrea -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-09 15:35 ` Andrea Corallo @ 2019-10-09 19:41 ` Stefan Monnier 2019-10-09 20:02 ` Andrea Corallo 0 siblings, 1 reply; 20+ messages in thread From: Stefan Monnier @ 2019-10-09 19:41 UTC (permalink / raw) To: Andrea Corallo; +Cc: Nicolas Petton, emacs-devel > I've repeated the same test going up two magnitude orders (1000000 > iterations). Still the execution time (~1.7secs) seems not distinguishable > between the old and the implementation. Great, then it looks like we have a winner! > For my curiosity I've also tried to run it using > `benchmark-run-compiled' with a very similar execution time as > result. I would have expected to have the unrolled version faster but > apparently funcall is not the bottle-neck here. Based on previous experience with defmethod's dispatch, I suspect that the main bottleneck may be in the time it takes to turn the arglist into a proper list and then to pass it to `apply` (those two steps happen within the "wrappers" built by `defmethod` and which decide which method to call). Stefan ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-09 19:41 ` Stefan Monnier @ 2019-10-09 20:02 ` Andrea Corallo 2019-10-10 8:27 ` Nicolas Petton 2019-10-10 8:28 ` Nicolas Petton 0 siblings, 2 replies; 20+ messages in thread From: Andrea Corallo @ 2019-10-09 20:02 UTC (permalink / raw) To: Stefan Monnier; +Cc: Nicolas Petton, emacs-devel Stefan Monnier <monnier@iro.umontreal.ca> writes: >> I've repeated the same test going up two magnitude orders (1000000 >> iterations). Still the execution time (~1.7secs) seems not distinguishable >> between the old and the implementation. > > Great, then it looks like we have a winner! Yes, feel free to come up with other suggestions on the patch or upstream it if you like (I've no write access). Bests Andrea -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-09 20:02 ` Andrea Corallo @ 2019-10-10 8:27 ` Nicolas Petton 2019-10-10 8:28 ` Nicolas Petton 1 sibling, 0 replies; 20+ messages in thread From: Nicolas Petton @ 2019-10-10 8:27 UTC (permalink / raw) To: Andrea Corallo, Stefan Monnier; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 246 bytes --] Andrea Corallo <akrl@sdf.org> writes: Hi, >> Great, then it looks like we have a winner! > > Yes, feel free to come up with other suggestions on the patch or > upstream it if you like (I've no write access). It looks good to me! Thanks, Nico [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 487 bytes --] ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-09 20:02 ` Andrea Corallo 2019-10-10 8:27 ` Nicolas Petton @ 2019-10-10 8:28 ` Nicolas Petton 2019-10-10 10:06 ` Andrea Corallo 1 sibling, 1 reply; 20+ messages in thread From: Nicolas Petton @ 2019-10-10 8:28 UTC (permalink / raw) To: Andrea Corallo, Stefan Monnier; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 216 bytes --] Andrea Corallo <akrl@sdf.org> writes: > Yes, feel free to come up with other suggestions on the patch or > upstream it if you like (I've no write access). Could you add tests to map-tests.el as well? Cheers, Nico [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 487 bytes --] ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-10 8:28 ` Nicolas Petton @ 2019-10-10 10:06 ` Andrea Corallo 2019-10-10 11:47 ` Nicolas Petton 2019-10-11 16:19 ` Stefan Monnier 0 siblings, 2 replies; 20+ messages in thread From: Andrea Corallo @ 2019-10-10 10:06 UTC (permalink / raw) To: Nicolas Petton; +Cc: Stefan Monnier, emacs-devel [-- Attachment #1: Type: text/plain, Size: 321 bytes --] Nicolas Petton <nico@petton.fr> writes: > Andrea Corallo <akrl@sdf.org> writes: > >> Yes, feel free to come up with other suggestions on the patch or >> upstream it if you like (I've no write access). > > Could you add tests to map-tests.el as well? > > Cheers, > Nico Sure, attached. Bests Andrea -- akrl@sdf.org [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #2: 0001-Extend-map-into-for-better-control-on-hash-table-cre.patch --] [-- Type: text/x-patch, Size: 4304 bytes --] From 7a1b42b1b58f7b0ee20ef24e9e73bce045a1987b Mon Sep 17 00:00:00 2001 From: Andrea Corallo <akrl@sdf.org> Date: Sun, 6 Oct 2019 22:43:11 +0200 Subject: [PATCH] Extend 'map-into' for better control on hash table creation. --- etc/NEWS | 4 ++++ lisp/emacs-lisp/map.el | 29 +++++++++++++++++++++-------- test/lisp/emacs-lisp/map-tests.el | 5 ++++- 3 files changed, 29 insertions(+), 9 deletions(-) diff --git a/etc/NEWS b/etc/NEWS index c8cc753..5942a32 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -24,6 +24,10 @@ applies, and please also update docstrings as needed. \f * Installation Changes in Emacs 27.1 +** Extend function 'map-into'. +Add a 'map-into' method to have hash table creation parameters +tweak-able. + ** Emacs now uses GMP, the GNU Multiple Precision library. By default, if 'configure' does not find a suitable libgmp, it arranges for the included mini-gmp library to be built and used. diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el index 54e802e..dfc1500 100644 --- a/lisp/emacs-lisp/map.el +++ b/lisp/emacs-lisp/map.el @@ -338,7 +338,8 @@ map-every-p t)) (defun map-merge (type &rest maps) - "Merge into a map of type TYPE all the key/value pairs in MAPS." + "Merge into a map of type TYPE all the key/value pairs in MAPS. +See `map-into' for all supported values of TYPE." (let ((result (map-into (pop maps) type))) (while maps ;; FIXME: When `type' is `list', we get an O(N^2) behavior. @@ -354,7 +355,8 @@ map-merge-with "Merge into a map of type TYPE all the key/value pairs in MAPS. When two maps contain the same key (`eql'), call FUNCTION on the two values and use the value returned by it. -MAP can be a list, hash-table or array." +MAP can be a list, hash-table or array. +See `map-into' for all supported values of TYPE." (let ((result (map-into (pop maps) type)) (not-found (cons nil nil))) (while maps @@ -458,17 +460,28 @@ map-do (funcall function index elt)) array)) -(cl-defmethod map-into (map (_type (eql hash-table))) - "Convert MAP into a hash-table." - ;; FIXME: Just knowing we want a hash-table is insufficient, since that - ;; doesn't tell us the test function to use with it! - (let ((ht (make-hash-table :size (map-length map) - :test 'equal))) +(defsubst map--into-hash (map keyword-args) + "Convert MAP into a hash-table. +KEYWORD-ARGS are forwarded to `make-hash-table'." + (let ((ht (apply #'make-hash-table keyword-args))) (map-apply (lambda (key value) (setf (map-elt ht key) value)) map) ht)) +(cl-defmethod map-into (map (_type (eql hash-table))) + "Convert MAP into a hash-table." + (map--into-hash map (list :size (map-length map) :test 'equal))) + +(cl-defmethod map-into (map (args (head hash-table))) + "Convert MAP into a hash-table. +ARGS is a list where the car is 'hash-table' and the cdr are the keyword-args + forwarded to `make-hash-table'. + +Example: + (map-into '((1 . 3)) '(hash-table :test eql))" + (map--into-hash map (cdr args))) + (defun map--make-pcase-bindings (args) "Return a list of pcase bindings from ARGS to the elements of a map." (seq-map (lambda (elt) diff --git a/test/lisp/emacs-lisp/map-tests.el b/test/lisp/emacs-lisp/map-tests.el index a54af80..9f61511 100644 --- a/test/lisp/emacs-lisp/map-tests.el +++ b/test/lisp/emacs-lisp/map-tests.el @@ -340,7 +340,8 @@ test-map-every-p (ert-deftest test-map-into () (let* ((alist '((a . 1) (b . 2))) - (ht (map-into alist 'hash-table))) + (ht (map-into alist 'hash-table)) + (ht2 (map-into alist '(hash-table :test eq)))) (should (hash-table-p ht)) (should (equal (map-into (map-into alist 'hash-table) 'list) alist)) @@ -349,6 +350,8 @@ test-map-into (map-keys ht))) (should (equal (map-values (map-into (map-into ht 'list) 'hash-table)) (map-values ht))) + (should (equal (map-into ht 'alist) (map-into ht2 'alist))) + (should (eq (hash-table-test ht2) 'eq)) (should (null (map-into nil 'list))) (should (map-empty-p (map-into nil 'hash-table))) (should-error (map-into [1 2 3] 'string)))) -- 2.7.4 ^ permalink raw reply related [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-10 10:06 ` Andrea Corallo @ 2019-10-10 11:47 ` Nicolas Petton 2019-10-11 16:19 ` Stefan Monnier 1 sibling, 0 replies; 20+ messages in thread From: Nicolas Petton @ 2019-10-10 11:47 UTC (permalink / raw) To: Andrea Corallo, Nicolas Petton; +Cc: Stefan Monnier, emacs-devel [-- Attachment #1: Type: text/plain, Size: 88 bytes --] Andrea Corallo <akrl@sdf.org> writes: > Sure, > attached. Excellent, thank you! Nico [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 487 bytes --] ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-10 10:06 ` Andrea Corallo 2019-10-10 11:47 ` Nicolas Petton @ 2019-10-11 16:19 ` Stefan Monnier 2019-10-11 16:29 ` Andrea Corallo 1 sibling, 1 reply; 20+ messages in thread From: Stefan Monnier @ 2019-10-11 16:19 UTC (permalink / raw) To: Andrea Corallo; +Cc: emacs-devel, Nicolas Petton > attached. Thanks, installed into `master` with minor tweaks (e.g. the NEWS entry was misplaced, and I changed the defsubst into a defun because the function itself contains a loop so the overhead of the function call is unlikely to be significant in proportion). Stefan > From 7a1b42b1b58f7b0ee20ef24e9e73bce045a1987b Mon Sep 17 00:00:00 2001 > From: Andrea Corallo <akrl@sdf.org> > Date: Sun, 6 Oct 2019 22:43:11 +0200 > Subject: [PATCH] Extend 'map-into' for better control on hash table creation. > > --- > etc/NEWS | 4 ++++ > lisp/emacs-lisp/map.el | 29 +++++++++++++++++++++-------- > test/lisp/emacs-lisp/map-tests.el | 5 ++++- > 3 files changed, 29 insertions(+), 9 deletions(-) > > diff --git a/etc/NEWS b/etc/NEWS > index c8cc753..5942a32 100644 > --- a/etc/NEWS > +++ b/etc/NEWS > @@ -24,6 +24,10 @@ applies, and please also update docstrings as needed. > \f > * Installation Changes in Emacs 27.1 > > +** Extend function 'map-into'. > +Add a 'map-into' method to have hash table creation parameters > +tweak-able. > + > ** Emacs now uses GMP, the GNU Multiple Precision library. > By default, if 'configure' does not find a suitable libgmp, it > arranges for the included mini-gmp library to be built and used. > diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el > index 54e802e..dfc1500 100644 > --- a/lisp/emacs-lisp/map.el > +++ b/lisp/emacs-lisp/map.el > @@ -338,7 +338,8 @@ map-every-p > t)) > > (defun map-merge (type &rest maps) > - "Merge into a map of type TYPE all the key/value pairs in MAPS." > + "Merge into a map of type TYPE all the key/value pairs in MAPS. > +See `map-into' for all supported values of TYPE." > (let ((result (map-into (pop maps) type))) > (while maps > ;; FIXME: When `type' is `list', we get an O(N^2) behavior. > @@ -354,7 +355,8 @@ map-merge-with > "Merge into a map of type TYPE all the key/value pairs in MAPS. > When two maps contain the same key (`eql'), call FUNCTION on the two > values and use the value returned by it. > -MAP can be a list, hash-table or array." > +MAP can be a list, hash-table or array. > +See `map-into' for all supported values of TYPE." > (let ((result (map-into (pop maps) type)) > (not-found (cons nil nil))) > (while maps > @@ -458,17 +460,28 @@ map-do > (funcall function index elt)) > array)) > > -(cl-defmethod map-into (map (_type (eql hash-table))) > - "Convert MAP into a hash-table." > - ;; FIXME: Just knowing we want a hash-table is insufficient, since that > - ;; doesn't tell us the test function to use with it! > - (let ((ht (make-hash-table :size (map-length map) > - :test 'equal))) > +(defsubst map--into-hash (map keyword-args) > + "Convert MAP into a hash-table. > +KEYWORD-ARGS are forwarded to `make-hash-table'." > + (let ((ht (apply #'make-hash-table keyword-args))) > (map-apply (lambda (key value) > (setf (map-elt ht key) value)) > map) > ht)) > > +(cl-defmethod map-into (map (_type (eql hash-table))) > + "Convert MAP into a hash-table." > + (map--into-hash map (list :size (map-length map) :test 'equal))) > + > +(cl-defmethod map-into (map (args (head hash-table))) > + "Convert MAP into a hash-table. > +ARGS is a list where the car is 'hash-table' and the cdr are the keyword-args > + forwarded to `make-hash-table'. > + > +Example: > + (map-into '((1 . 3)) '(hash-table :test eql))" > + (map--into-hash map (cdr args))) > + > (defun map--make-pcase-bindings (args) > "Return a list of pcase bindings from ARGS to the elements of a map." > (seq-map (lambda (elt) > diff --git a/test/lisp/emacs-lisp/map-tests.el b/test/lisp/emacs-lisp/map-tests.el > index a54af80..9f61511 100644 > --- a/test/lisp/emacs-lisp/map-tests.el > +++ b/test/lisp/emacs-lisp/map-tests.el > @@ -340,7 +340,8 @@ test-map-every-p > > (ert-deftest test-map-into () > (let* ((alist '((a . 1) (b . 2))) > - (ht (map-into alist 'hash-table))) > + (ht (map-into alist 'hash-table)) > + (ht2 (map-into alist '(hash-table :test eq)))) > (should (hash-table-p ht)) > (should (equal (map-into (map-into alist 'hash-table) 'list) > alist)) > @@ -349,6 +350,8 @@ test-map-into > (map-keys ht))) > (should (equal (map-values (map-into (map-into ht 'list) 'hash-table)) > (map-values ht))) > + (should (equal (map-into ht 'alist) (map-into ht2 'alist))) > + (should (eq (hash-table-test ht2) 'eq)) > (should (null (map-into nil 'list))) > (should (map-empty-p (map-into nil 'hash-table))) > (should-error (map-into [1 2 3] 'string)))) ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH] extend map-into 2019-10-11 16:19 ` Stefan Monnier @ 2019-10-11 16:29 ` Andrea Corallo 0 siblings, 0 replies; 20+ messages in thread From: Andrea Corallo @ 2019-10-11 16:29 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-devel, Nicolas Petton Stefan Monnier <monnier@iro.umontreal.ca> writes: >> attached. > > Thanks, installed into `master` with minor tweaks (e.g. the NEWS entry > was misplaced, and I changed the defsubst into a defun because the > function itself contains a loop so the overhead of the function call is > unlikely to be significant in proportion). > > > Stefan Cool thanks! Bests Andrea > >> From 7a1b42b1b58f7b0ee20ef24e9e73bce045a1987b Mon Sep 17 00:00:00 2001 >> From: Andrea Corallo <akrl@sdf.org> >> Date: Sun, 6 Oct 2019 22:43:11 +0200 >> Subject: [PATCH] Extend 'map-into' for better control on hash table creation. >> >> --- >> etc/NEWS | 4 ++++ >> lisp/emacs-lisp/map.el | 29 +++++++++++++++++++++-------- >> test/lisp/emacs-lisp/map-tests.el | 5 ++++- >> 3 files changed, 29 insertions(+), 9 deletions(-) >> >> diff --git a/etc/NEWS b/etc/NEWS >> index c8cc753..5942a32 100644 >> --- a/etc/NEWS >> +++ b/etc/NEWS >> @@ -24,6 +24,10 @@ applies, and please also update docstrings as needed. >> \f >> * Installation Changes in Emacs 27.1 >> >> +** Extend function 'map-into'. >> +Add a 'map-into' method to have hash table creation parameters >> +tweak-able. >> + >> ** Emacs now uses GMP, the GNU Multiple Precision library. >> By default, if 'configure' does not find a suitable libgmp, it >> arranges for the included mini-gmp library to be built and used. >> diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el >> index 54e802e..dfc1500 100644 >> --- a/lisp/emacs-lisp/map.el >> +++ b/lisp/emacs-lisp/map.el >> @@ -338,7 +338,8 @@ map-every-p >> t)) >> >> (defun map-merge (type &rest maps) >> - "Merge into a map of type TYPE all the key/value pairs in MAPS." >> + "Merge into a map of type TYPE all the key/value pairs in MAPS. >> +See `map-into' for all supported values of TYPE." >> (let ((result (map-into (pop maps) type))) >> (while maps >> ;; FIXME: When `type' is `list', we get an O(N^2) behavior. >> @@ -354,7 +355,8 @@ map-merge-with >> "Merge into a map of type TYPE all the key/value pairs in MAPS. >> When two maps contain the same key (`eql'), call FUNCTION on the two >> values and use the value returned by it. >> -MAP can be a list, hash-table or array." >> +MAP can be a list, hash-table or array. >> +See `map-into' for all supported values of TYPE." >> (let ((result (map-into (pop maps) type)) >> (not-found (cons nil nil))) >> (while maps >> @@ -458,17 +460,28 @@ map-do >> (funcall function index elt)) >> array)) >> >> -(cl-defmethod map-into (map (_type (eql hash-table))) >> - "Convert MAP into a hash-table." >> - ;; FIXME: Just knowing we want a hash-table is insufficient, since that >> - ;; doesn't tell us the test function to use with it! >> - (let ((ht (make-hash-table :size (map-length map) >> - :test 'equal))) >> +(defsubst map--into-hash (map keyword-args) >> + "Convert MAP into a hash-table. >> +KEYWORD-ARGS are forwarded to `make-hash-table'." >> + (let ((ht (apply #'make-hash-table keyword-args))) >> (map-apply (lambda (key value) >> (setf (map-elt ht key) value)) >> map) >> ht)) >> >> +(cl-defmethod map-into (map (_type (eql hash-table))) >> + "Convert MAP into a hash-table." >> + (map--into-hash map (list :size (map-length map) :test 'equal))) >> + >> +(cl-defmethod map-into (map (args (head hash-table))) >> + "Convert MAP into a hash-table. >> +ARGS is a list where the car is 'hash-table' and the cdr are the keyword-args >> + forwarded to `make-hash-table'. >> + >> +Example: >> + (map-into '((1 . 3)) '(hash-table :test eql))" >> + (map--into-hash map (cdr args))) >> + >> (defun map--make-pcase-bindings (args) >> "Return a list of pcase bindings from ARGS to the elements of a map." >> (seq-map (lambda (elt) >> diff --git a/test/lisp/emacs-lisp/map-tests.el b/test/lisp/emacs-lisp/map-tests.el >> index a54af80..9f61511 100644 >> --- a/test/lisp/emacs-lisp/map-tests.el >> +++ b/test/lisp/emacs-lisp/map-tests.el >> @@ -340,7 +340,8 @@ test-map-every-p >> >> (ert-deftest test-map-into () >> (let* ((alist '((a . 1) (b . 2))) >> - (ht (map-into alist 'hash-table))) >> + (ht (map-into alist 'hash-table)) >> + (ht2 (map-into alist '(hash-table :test eq)))) >> (should (hash-table-p ht)) >> (should (equal (map-into (map-into alist 'hash-table) 'list) >> alist)) >> @@ -349,6 +350,8 @@ test-map-into >> (map-keys ht))) >> (should (equal (map-values (map-into (map-into ht 'list) 'hash-table)) >> (map-values ht))) >> + (should (equal (map-into ht 'alist) (map-into ht2 'alist))) >> + (should (eq (hash-table-test ht2) 'eq)) >> (should (null (map-into nil 'list))) >> (should (map-empty-p (map-into nil 'hash-table))) >> (should-error (map-into [1 2 3] 'string)))) > > -- akrl@sdf.org ^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2019-10-11 16:29 UTC | newest] Thread overview: 20+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2019-10-04 9:58 new function proposal alist-to-hash Andrea Corallo 2019-10-04 19:16 ` Stefan Monnier 2019-10-05 8:18 ` Andrea Corallo 2019-10-05 15:13 ` Stefan Monnier 2019-10-05 15:45 ` Andrea Corallo 2019-10-05 8:28 ` [PATCH] extend map-into (was: new function proposal alist-to-hash) Andrea Corallo 2019-10-06 14:02 ` [PATCH] extend map-into Stefan Monnier 2019-10-06 20:59 ` Andrea Corallo 2019-10-08 17:29 ` Stefan Monnier 2019-10-08 18:46 ` Andrea Corallo 2019-10-08 20:23 ` Stefan Monnier 2019-10-09 15:35 ` Andrea Corallo 2019-10-09 19:41 ` Stefan Monnier 2019-10-09 20:02 ` Andrea Corallo 2019-10-10 8:27 ` Nicolas Petton 2019-10-10 8:28 ` Nicolas Petton 2019-10-10 10:06 ` Andrea Corallo 2019-10-10 11:47 ` Nicolas Petton 2019-10-11 16:19 ` Stefan Monnier 2019-10-11 16:29 ` Andrea Corallo
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.