automat
automat copied to clipboard
Published
20 hours ago •
ztellman
ztellman
Automat "slow"
We discussed this on Slack briefly. I got this using a plain clojure.main repl. I've generated a few data sets using test.check, I've used 1055 as the length of input.
user=> (require '[automat.core :as a]
'[criterium.core :as c])
user=> (let [data "7Z0YzI6qmKUR4QNOq81l409AC2Ng3c00tb9J4VOz5kBuGTqCAWmYTx4E7Xckp6662k0jd14ds9G1jt0ldShcf37POcfYqsPcqliwlcM0l6GYVF3850650biK89QL3N68Z19k57Eu3dLSukaWZCM32J3Dz99l4KF53JvkWraBwlX3FpU3TWM3X992a1tU2qL6q6Y0g4r4ay5QMuc1twL9xRJMn3WoeA7g8Oh3FoYMX3VD02FhaB76TwMm5kxf2mxK5HUmDu88gYsO4CS6paOqEf7s17hJ712y3xaCT9a3r71M4E2467jr0i4uGt267HMKQO7dqHywM8CFy72AIUq7OZ4K5Nn2t9JuL5Kqv79Y8ZE3aAS4tNeG8ckh201AfB11okTh5bT9oann21A6wN67vzq3Q31SyF5wg2Xx1885z56X4WLgkRfq5A3kFgmqAJdfmlcTp5Dr4404P2nWGmDBJ62dR100RQtLLjKN25a42Kebk1pWFbu6z56y5jHE0txpN9V87cb66Exp50Cg42Jl37Mbi2MqkW218LjNMTnRU7365RT8Uf3523X1cCZFWq7z2GSkc6uL2ai2d88B7a7i1k0h0d9K63765p3w4obwd32kIlQu5xy4yFQ3R91XP353c8J7H3Ep3Oo45p8F70y3649hqM310Gnv13gBXHdLyXs25od8tmwE5fHB3G06OaG877ymRI5J89KI1XylAx47o18H17CHC6P5fm6KC71n40WjK01P4rt06K06F8TM6OF81eq3wE4W0AO702PxEO042I4r9VUt8g0jp3057Sbju25U15HCP1742NEVTM1niDjb0S89885Nf93X97Cgsw5x3eu13ZU8cGbj246qt5t7lzzW08ozl1yykx73d7a74VNPYdZE4498XTgnzhv3R44p6iulMm9Vauv9sXG2Hb4TH4Kx9G6hK1X2MJEsHFm680ZueWNu98G3oVnA435SfwSA6umdt26g9hBoTGMXZ7K64yIs8kYxgwKi0Jqhvm3wdTJdn86u9HX5TeQh45Vc6TSZeCW2xLxNagu"
fsm (a/compile [\f \o \o])]
(c/bench
(reduce
#(a/advance fsm %1 %2 false)
nil
data)))
Evaluation count : 339480 in 60 samples of 5658 calls.
Execution time mean : 178.169999 µs
Execution time std-deviation : 2.128803 µs
Execution time lower quantile : 176.386367 µs ( 2.5%)
Execution time upper quantile : 182.867510 µs (97.5%)
Overhead used : 1.727016 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 1 (1.6667 %)
low-mild 3 (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
If I'm not being daft, which is common enough, (/ 178.16 1055) is 0.169µs = 169ns per advancement.
Numbers have a similar result:
user=> (let [data [-3 25 1 -14 -2 15 -18 -11 30 3 -30 17 24 -20 27 13 -1 -17 -15 -23 -24 -25 22 11 12 -8 -24 10 11 14 18 -10 -10 19 -28 27 -26 -8 1 -22 20 4 -12 -13 -15 13 27 -8 30 -7 21 -5 25 -28 10 4 -18 24 3 -16 -20 -22 22 -28 -8 25 -29 -13 -16 -24 -9 1 1 7 -9 7 -26 -5 5 -2 19 25 29 25 -4 20 1 21 -3 21 -13 -11 -15 2 -3 -17 28 -12 -10 15 -7 -28 14 2 13 18 17 -17 7 1 17 11 23 -16 -8 22 -28 21 28 1 18 7 26 27 5 -14 7 16 -7 -21 -7 10 5 5 20 24 30 30 17 27 16 -17 -18 21 -9 -3 -30 3 -25 -24 7 25 22 -18 -3 -12 -8 14 -20 -4 15 7 -19 23 -29 2 1 29 -12 24 19 18 16 -17 20 27 -26 18 -26 16 -17 13 24 29 -23 21 -7 1 -2 -15 -6 17 19 5 -18 30 -7 5 2 -1 3 6 -24 3 -13 -18 5 4 6 -5 7 10 22 7 30 -9 6 -16 -27 22 26 -15 17 14 -10 24 -22 17 20 30 5 14 17 -26 -6 17 23 18 6 1 -25 -15 -29 -7 -20 -23 3 1 23 -1 22 -15 -11 2 -22 12 16 28 24 4 12 -11 -8 1 23 10 0 20 25 -9 -17 21 -21 10 7 -7 5 11 -8 -11 -15 29 8 -29 -24 -14 17 -19 -17 -18 16 16 3 13 -19 7 27 -29 15 -21 -26 24 2 10 -27 -26 13 17 29 -14 0 -26 -2 10 18 0 25 23 8 21 6 -6 -18 5 16 19 23 26 24 -27 -26 -11 -3 -17 -12 23 21 12 23 22 20 -27 -3 -3 15 -1 -20 5 -13 -21 30 -6 -18 -24 -4 20 -30 -15 -28 23 10 27 3 -21 18 -12 1 23 16 4 3 29 -27 -2 15 -26 2 -9 -14 28 18 -25 9 -17 7 -23 -29 -14 -23 -7 -25 16 3 -1 -27 -14 7 -25 28 -11 -27 -15 -27 -6 19 19 -15 -5 26 -9 -28 -4 7 -20 -26 7 8 28 0 14 -21 -16 6 30 10 -21 0 -8 -2 -25 -18 -21 20 -27 24 8 -22 18 -20 8 -10 -29 6 9 -7 4 -11 -17 -21 -4 -16 15 3 10 -23 8 -26 3 20 28 -3 25 20 -28 -28 5 -11 24 -3 -29 -21 27 -20 -12 2 3 22 25 22 25 29 3 26 27 -16 -10 30 25 -28 26 -13 -24 -16 -2 10 11 11 -2 -24 18 -22 14 -30 -25 -5 -23 -28 18 28 10 -16 6 7 -8 -22 23 -13 11 21 -3 -24 -4 22 -13 -8 27 -13 19 -29 10 -6 -7 -5 9 13 -19 -1 -9 30 -2 2 21 -13 9 -12 -5 -26 12 7 -23 20 -29 2 27 5 -14 14 2 14 2 -9 17 -13 -24 -9 -6 11 -6 -26 -27 -13 -1 28 -23 -19 22 3 -29 2 -13 9 -1 11 30 3 5 -17 -18 28 26 28 -9 -20 15 -4 -19 -14 -18 -8 -17 -22 -29 -24 20 12 12 16 7 -25 -6 14 0 -15 14 20 -25 23 10 -29 8 14 -19 -20 -3 25 -3 -7 -19 -11 0 -29 24 27 -28 -28 22 -17 27 12 -24 -26 -19 14 17 -25 -7 -13 18 28 21 24 22 -25 25 -18 -15 -2 25 26 -17 20 15 -7 30 18 20 -14 -12 -16 10 23 -27 -7 -14 -8 -8 -12 24 6 -4 30 -16 14 4 -15 27 -17 -14 -24 29 29 18 -7 -15 28 -11 7 6 18 30 -25 22 -2 -20 1 -23 -13 -28 -4 26 18 25 22 -18 -5 -25 -7 5 30 -1 -7 -8 -30 24 -13 19 18 26 1 -16 1 -1 25 16 10 9 1 12 -28 5 -27 -16 14 24 18 -1 -12 25 -19 30 24 -21 27 18 -10 -14 -7 -12 -26 -9 13 23 10 -6 1 -7 -16 25 20 -22 11 12 20 4 14 -6 18 19 5 -6 14 -29 -26 21 11 30 19 -24 -12 -6 -27 25 14 -1 25 -12 18 -17 0 -29 -24 -30 5 -20 29 24 -17 28 -11 -10 7 11 7 -22 2 21 14 -15 -29 8 16 16 10 9 -10 16 30 12 -2 -18 9 5 -20 13 10 -29 17 11 22 22 -27 -3 -9 -19 22 11 15 -22 -15 11 -27 15 15 -26 6 -2 2 16 16 -7 -1 -7 -2 -17 20 -12 -13 18 8 7 -3 9 30 13 -19 -4 -13 7 -12 24 -7 8 10 -5 14 6 26 -18 -21 -1 -4 28 4 2 -13 21 15 -4 12 6 -20 -6 23 -21 8 22 22 5 23 -12 -23 -16 -11 7 -12 20 -24 10 -23 16 7 20 3 -1 26 -24 23 -21 -9 27 -3 -23 -30 22 16 12 3 10 -14 -17 -6 16 -16 -17 -2 5 13 -6 23 27 -26 15 -7 21 -14 14 12 -8 -13 23 -5 -27 30 27 -5 26 29 29 28 1 -15 -26 20 30 17 1 2 -1 -3 13 13 -10 -13 13 -7 -15 -14 -26 -11 -3 1 21 -16 11 23 -1 6 17 19 2 2 -14 3 -27 9 2 14 -18 -30 22 3 -2 19 -26 30 29 -24 -16 -2 5 -6 -13 -21 -20 -17 23 15 30 15 -12 -5 -18 8 -2 -9 -13 -24 -20 -26 -27 -9 21 -30 -10 4 -27 22 25 18 8 -28 -16 6 30 -2]
fsm (a/compile [50 20 10])]
(c/bench
(reduce
#(a/advance fsm %1 %2 false)
nil
data)))
Evaluation count : 446280 in 60 samples of 7438 calls.
Execution time mean : 139.068076 µs
Execution time std-deviation : 12.810401 µs
Execution time lower quantile : 134.080157 µs ( 2.5%)
Execution time upper quantile : 168.040733 µs (97.5%)
Overhead used : 1.727016 ns
Found 9 outliers in 60 samples (15.0000 %)
low-severe 1 (1.6667 %)
low-mild 8 (13.3333 %)
Variance from outliers : 65.3027 % Variance is severely inflated by outliers
nil
This is with this java:
❯ java -version
openjdk version "1.8.0_152"
OpenJDK Runtime Environment (build 1.8.0_152-b03)
OpenJDK 64-Bit Server VM (build 25.152-b03, mixed mode)
and clojure version 1.8.
I also tried with Oracle JDK:
user=> (let [data [-3 25 1 -14 -2 15 -18 -11 30 3 -30 17 24 -20 27 13 -1 -17 -15 -23 -24 -25 22 11 12 -8 -24 10 11 14 18 -10 -10 19 -28 27 -26 -8 1 -22 20 4 -12 -13 -15 13 27 -8 30 -7 21 -5 25 -28 10 4 -18 24 3 -16 -20 -22 22 -28 -8 25 -29 -13 -16 -24 -9 1 1 7 -9 7 -26 -5 5 -2 19 25 29 25 -4 20 1 21 -3 21 -13 -11 -15 2 -3 -17 28 -12 -10 15 -7 -28 14 2 13 18 17 -17 7 1 17 11 23 -16 -8 22 -28 21 28 1 18 7 26 27 5 -14 7 16 -7 -21 -7 10 5 5 20 24 30 30 17 27 16 -17 -18 21 -9 -3 -30 3 -25 -24 7 25 22 -18 -3 -12 -8 14 -20 -4 15 7 -19 23 -29 2 1 29 -12 24 19 18 16 -17 20 27 -26 18 -26 16 -17 13 24 29 -23 21 -7 1 -2 -15 -6 17 19 5 -18 30 -7 5 2 -1 3 6 -24 3 -13 -18 5 4 6 -5 7 10 22 7 30 -9 6 -16 -27 22 26 -15 17 14 -10 24 -22 17 20 30 5 14 17 -26 -6 17 23 18 6 1 -25 -15 -29 -7 -20 -23 3 1 23 -1 22 -15 -11 2 -22 12 16 28 24 4 12 -11 -8 1 23 10 0 20 25 -9 -17 21 -21 10 7 -7 5 11 -8 -11 -15 29 8 -29 -24 -14 17 -19 -17 -18 16 16 3 13 -19 7 27 -29 15 -21 -26 24 2 10 -27 -26 13 17 29 -14 0 -26 -2 10 18 0 25 23 8 21 6 -6 -18 5 16 19 23 26 24 -27 -26 -11 -3 -17 -12 23 21 12 23 22 20 -27 -3 -3 15 -1 -20 5 -13 -21 30 -6 -18 -24 -4 20 -30 -15 -28 23 10 27 3 -21 18 -12 1 23 16 4 3 29 -27 -2 15 -26 2 -9 -14 28 18 -25 9 -17 7 -23 -29 -14 -23 -7 -25 16 3 -1 -27 -14 7 -25 28 -11 -27 -15 -27 -6 19 19 -15 -5 26 -9 -28 -4 7 -20 -26 7 8 28 0 14 -21 -16 6 30 10 -21 0 -8 -2 -25 -18 -21 20 -27 24 8 -22 18 -20 8 -10 -29 6 9 -7 4 -11 -17 -21 -4 -16 15 3 10 -23 8 -26 3 20 28 -3 25 20 -28 -28 5 -11 24 -3 -29 -21 27 -20 -12 2 3 22 25 22 25 29 3 26 27 -16 -10 30 25 -28 26 -13 -24 -16 -2 10 11 11 -2 -24 18 -22 14 -30 -25 -5 -23 -28 18 28 10 -16 6 7 -8 -22 23 -13 11 21 -3 -24 -4 22 -13 -8 27 -13 19 -29 10 -6 -7 -5 9 13 -19 -1 -9 30 -2 2 21 -13 9 -12 -5 -26 12 7 -23 20 -29 2 27 5 -14 14 2 14 2 -9 17 -13 -24 -9 -6 11 -6 -26 -27 -13 -1 28 -23 -19 22 3 -29 2 -13 9 -1 11 30 3 5 -17 -18 28 26 28 -9 -20 15 -4 -19 -14 -18 -8 -17 -22 -29 -24 20 12 12 16 7 -25 -6 14 0 -15 14 20 -25 23 10 -29 8 14 -19 -20 -3 25 -3 -7 -19 -11 0 -29 24 27 -28 -28 22 -17 27 12 -24 -26 -19 14 17 -25 -7 -13 18 28 21 24 22 -25 25 -18 -15 -2 25 26 -17 20 15 -7 30 18 20 -14 -12 -16 10 23 -27 -7 -14 -8 -8 -12 24 6 -4 30 -16 14 4 -15 27 -17 -14 -24 29 29 18 -7 -15 28 -11 7 6 18 30 -25 22 -2 -20 1 -23 -13 -28 -4 26 18 25 22 -18 -5 -25 -7 5 30 -1 -7 -8 -30 24 -13 19 18 26 1 -16 1 -1 25 16 10 9 1 12 -28 5 -27 -16 14 24 18 -1 -12 25 -19 30 24 -21 27 18 -10 -14 -7 -12 -26 -9 13 23 10 -6 1 -7 -16 25 20 -22 11 12 20 4 14 -6 18 19 5 -6 14 -29 -26 21 11 30 19 -24 -12 -6 -27 25 14 -1 25 -12 18 -17 0 -29 -24 -30 5 -20 29 24 -17 28 -11 -10 7 11 7 -22 2 21 14 -15 -29 8 16 16 10 9 -10 16 30 12 -2 -18 9 5 -20 13 10 -29 17 11 22 22 -27 -3 -9 -19 22 11 15 -22 -15 11 -27 15 15 -26 6 -2 2 16 16 -7 -1 -7 -2 -17 20 -12 -13 18 8 7 -3 9 30 13 -19 -4 -13 7 -12 24 -7 8 10 -5 14 6 26 -18 -21 -1 -4 28 4 2 -13 21 15 -4 12 6 -20 -6 23 -21 8 22 22 5 23 -12 -23 -16 -11 7 -12 20 -24 10 -23 16 7 20 3 -1 26 -24 23 -21 -9 27 -3 -23 -30 22 16 12 3 10 -14 -17 -6 16 -16 -17 -2 5 13 -6 23 27 -26 15 -7 21 -14 14 12 -8 -13 23 -5 -27 30 27 -5 26 29 29 28 1 -15 -26 20 30 17 1 2 -1 -3 13 13 -10 -13 13 -7 -15 -14 -26 -11 -3 1 21 -16 11 23 -1 6 17 19 2 2 -14 3 -27 9 2 14 -18 -30 22 3 -2 19 -26 30 29 -24 -16 -2 5 -6 -13 -21 -20 -17 23 15 30 15 -12 -5 -18 8 -2 -9 -13 -24 -20 -26 -27 -9 21 -30 -10 4 -27 22 25 18 8 -28 -16 6 30 -2]
fsm (a/compile [50 20 10])]
(c/bench
(reduce
#(a/advance fsm %1 %2 false)
nil
data)))
Evaluation count : 428820 in 60 samples of 7147 calls.
Execution time mean : 140.780361 µs
Execution time std-deviation : 748.460193 ns
Execution time lower quantile : 139.914201 µs ( 2.5%)
Execution time upper quantile : 142.457726 µs (97.5%)
Overhead used : 1.727470 ns
Found 6 outliers in 60 samples (10.0000 %)
low-severe 6 (10.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
nil
❯ java -version
java version "1.8.0_144"
Java(TM) SE Runtime Environment (build 1.8.0_144-b01)
Java HotSpot(TM) 64-Bit Server VM (build 25.144-b01, mixed mode)
Is this enough detail? Anything else I can do?
Corrected some of my math which made automata look slower than it should.