Thanks for the feedback!
Glad to hear that it might be of interest.
I did some more tests this time in clojure:
;; test diff on one small change
(def m2 (zipmap (range 10000) (range 10000)))
(crit/quick-bench (diff-data m2 (assoc m2 42 :a)))
Execution time mean : 243,902630 µs
Execution time std-deviation : 3,602690 µs
Execution time lower quantile : 238,802702 µs ( 2,5%)
Execution time upper quantile : 247,509517 µs (97,5%)
Overhead used : 1,431409 ns
(crit/quick-bench (clojure.data/diff m2 (assoc m2 42 :a)))
Execution time mean : 33,313132 ms
Execution time std-deviation : 150,585629 µs
Execution time lower quantile : 33,081544 ms ( 2,5%)
Execution time upper quantile : 33,467179 ms (97,5%)
Overhead used : 1,431409 ns
;; test diff on equal but not identical
(crit/quick-bench (diff-data (zipmap (range 10000) (range 10000)) (zipmap
(range 10000) (range 10000))))
Execution time mean : 135,450677 ms
Execution time std-deviation : 2,530132 ms
Execution time lower quantile : 132,812801 ms ( 2,5%)
Execution time upper quantile : 138,229365 ms (97,5%)
Overhead used : 1,431409 ns
(crit/quick-bench (clojure.data/diff (zipmap (range 10000) (range 10000))
(zipmap (range 10000) (range 10000))))
Execution time mean : 9,241076 ms
Execution time std-deviation : 165,557224 µs
Execution time lower quantile : 8,985506 ms ( 2,5%)
Execution time upper quantile : 9,399309 ms (97,5%)
Overhead used : 1,431409 ns
This shows that when there are alot of changes the "new" algorithm is
slower as it needs to traverse the full tree.
But when there are few changes the "new" algorithm is faster.
(note; changed from identical? checks to = checks in the algorithm as it
otherwise would report the last test as unequal but that had no affect the
performance in these tests)
On Thursday, October 13, 2016 at 9:23:22 PM UTC+2, Alex Miller wrote:
>
>
>
> On Thursday, October 13, 2016 at 12:23:21 PM UTC-5, Dan wrote:
>>
>> Hi
>>
>> I would like to be able to take advantage of the tree structures
>> underneath e.g. hash-maps for a faster diff.
>>
>> I wrote a gist to do this in clojurescript
>> https://gist.github.com/danjohansson/add5515b2067b3036044d450cbec08f3
>> <https://www.google.com/url?q=https%3A%2F%2Fgist.github.com%2Fdanjohansson%2Fadd5515b2067b3036044d450cbec08f3&sa=D&sntz=1&usg=AFQjCNF2a7z_HTG_N0QBHQVUE9Iu8mhfaA>
>>
>> I guess BitmapIndexedNode etc are implementation details of
>> PersistentHashMaps and its a bad idea to use them directly.
>>
>
> Correct.
>
>
>> In clojure it is not straightforward to do this at all since root is
>> private.
>>
>
> Should be considered implementation details.
>
>
>> So to my question:
>> Is there or has there been any plans to add a diff or a diff enabler on
>> the data structures to be able to make faster diffs.
>>
>
> No.
>
> It seems like the "right" way to do such a thing would be to create an
> interface/protocol for diffing and extend/implement it on the data
> structures as directly as possible, which seems like the path you're going
> down.
>
> Given the perf diff you demonstrated (would be curious to see how that
> translates to Clojure), might be an interesting enhancement.
>
> Another option would be to look at optimizations for the existing generic
> data diff as well. Might guess is there is probably room for improvement.
>
>
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
