Skip to content

Instantly share code, notes, and snippets.

@samdphillips

samdphillips/profile_20191020-131252.txt

Forked from jackfirth/rebellion-sorting-benchmark.rkt
Last active October 20, 2019 21:01
Show Gist options
  • Save samdphillips/8c44d0c558b2f2761812d720e24140f6 to your computer and use it in GitHub Desktop.
Save samdphillips/8c44d0c558b2f2761812d720e24140f6 to your computer and use it in GitHub Desktop.
Download ZIP
Benchmark comparing Rebellion's sorting transducer against using `(take (sort (sequence->list seq) ...) ...)`
Raw
profile_20191020-131252.txt
Profiling results
-----------------
Total cpu time observed: 45238ms (out of 45309ms)
Number of samples taken: 796 (once every 57ms)
(Hiding functions with self<1.0% and local<2.0%: 7 of 61 hidden)
=======================================================================================
Caller
Idx Total Self Name+src Local%
ms(pct) ms(pct) Callee
=======================================================================================
for-loop [29] 0.6%
consume [4] 7.9%
transducer-position-advance [7] 9.8%
??? [3] 10.1%
...higher-order.rkt:372:44 [21] 12.1%
??? [8] 59.5%
[1] 9472(20.9%) 7376(16.3%) ??? ...ects/racket/contract/private/guts.rkt:774:8
comparison? [9] 22.1%
---------------------------------------------------------------------------------------
transducer-position-advance-repeatedly [19] 8.5%
compare [34] 8.6%
transducer-position-advance [7] 12.3%
??? [8] 15.3%
??? [3] 27.2%
??? [6] 28.0%
[2] 5216(11.5%) 5216(11.5%) ??? ...tract/private/arrow-higher-order.rkt:364:33
---------------------------------------------------------------------------------------
transducer-position-try-emit [32] 1.0%
??? [3] 1.5%
??? [8] 2.3%
wrapped-func [12] 3.6%
transducer-position-advance [7] 87.2%
[3] 29438(65.1%) 4024(8.9%) ??? ...tract/private/arrow-higher-order.rkt:360:33
consume [4] 77.1%
??? [1] 2.4%
??? [2] 2.3%
??? [3] 1.5%
??? [14] 1.2%
tree-trim-minimum [38] 0.7%
??? [16] 0.1%
---------------------------------------------------------------------------------------
??? [3] 100.0%
[4] 23706(52.4%) 3581(7.9%) consume ...on/private/transducer-sorting.rkt:161:2
??? [6] 67.6%
...higher-order.rkt:372:44 [21] 10.8%
??? [1] 3.1%
??? [14] 1.9%
---------------------------------------------------------------------------------------
??? [23] 100.0%
[5] 3030(6.7%) 3030(6.7%) for-loop ...acket/contract/private/list.rkt:212:15
---------------------------------------------------------------------------------------
for-loop [29] 3.0%
??? [6] 27.8%
consume [4] 69.1%
[6] 16700(36.9%) 3009(6.7%) ??? ...ellion/private/transducer-sorting.rkt:120:0
??? [8] 51.9%
??? [6] 27.8%
??? [2] 6.2%
---------------------------------------------------------------------------------------
??? [37] 0.7%
next-pos [54] 4.2%
transducer-position-advance-repeatedly [19] 95.1%
[7] 40806(90.2%) 2883(6.4%) transducer-position-advance ...ransducer.rkt:120:0
??? [3] 65.4%
??? [8] 19.0%
??? [53] 3.9%
??? [1] 2.3%
??? [2] 1.6%
??? [10] 0.7%
---------------------------------------------------------------------------------------
??? [37] 0.1%
in-transduced [49] 0.1%
loop [51] 0.1%
transducer-position-try-emit [32] 0.3%
transducer-position-advance-repeatedly [19] 1.0%
transducer-position-advance [7] 9.0%
??? [6] 14.2%
...ow-val-first.rkt:390:18 [45] 75.3%
[8] 43215(95.5%) 2606(5.8%) ??? ...contract/private/arrow-val-first.rkt:390:18
reduce-all [50] 72.2%
??? [1] 6.5%
wrapped-func [12] 4.8%
??? [23] 3.8%
loop [51] 3.1%
successfully-got-the-right-kind-of-function [11] 1.7%
arrow-higher-order:lnp [13] 1.7%
??? [2] 0.9%
??? [3] 0.8%
compare [34] 0.6%
---------------------------------------------------------------------------------------
??? [1] 100.0%
[9] 2096(4.6%) 2096(4.6%) comparison? ...bellion/private/comparator.rkt:44:0
---------------------------------------------------------------------------------------
transducer-position-advance [7] 22.0%
wrapped-func [12] 78.0%
[10] 1234(2.7%) 1234(2.7%) ??? ...tract/private/arrow-higher-order.rkt:348:46
---------------------------------------------------------------------------------------
??? [8] 100.0%
[11] 1413(3.1%) 1180(2.6%) successfully-got-the-right-kind-of-function ...1:4
arity-checking-wrapper [26] 16.5%
---------------------------------------------------------------------------------------
??? [8] 100.0%
[12] 4190(9.3%) 1028(2.3%) wrapped-func ...ellion/private/comparator.rkt:54:2
??? [3] 52.5%
??? [10] 23.0%
---------------------------------------------------------------------------------------
??? [8] 100.0%
[13] 1468(3.2%) 895(2.0%) arrow-higher-order:lnp ...w-higher-order.rkt:699:7
??? [17] 39.0%
---------------------------------------------------------------------------------------
??? [3] 43.3%
consume [4] 56.7%
[14] 784(1.7%) 784(1.7%) ??? ...v7.4/collects/racket/private/kw.rkt:1854:39
---------------------------------------------------------------------------------------
??? [16] 100.0%
[15] 693(1.5%) 693(1.5%) ??? ...lects/racket/contract/private/orc.rkt:83:14
---------------------------------------------------------------------------------------
??? [3] 8.8%
...higher-order.rkt:372:44 [21] 91.2%
[16] 1312(2.9%) 618(1.4%) ??? ...ects/racket/contract/private/prop.rkt:567:4
??? [15] 52.8%
---------------------------------------------------------------------------------------
arrow-higher-order:lnp [13] 100.0%
[17] 573(1.3%) 573(1.3%) ??? ...et/contract/private/arity-checking.rkt:19:2
---------------------------------------------------------------------------------------
random-sample/out-replacement [25] 100.0%
[18] 570(1.3%) 570(1.3%) for-loop ...t v7.4/collects/racket/random.rkt:70:2
---------------------------------------------------------------------------------------
??? [37] 100.0%
[19] 40712(90.0%) 564(1.2%) transducer-position-advance-repeatedly ...kt:108:0
transducer-position-advance [7] 95.3%
??? [8] 2.2%
??? [2] 1.1%
---------------------------------------------------------------------------------------
random-gemstone [22] 100.0%
[20] 511(1.1%) 397(0.9%) set ...collects/racket/private/set-types.rkt:982:0
for-loop [28] 22.3%
---------------------------------------------------------------------------------------
for-loop [29] 4.4%
consume [4] 95.6%
[21] 2680(5.9%) 342(0.8%) ...higher-order.rkt:372:44 (unknown source)
??? [16] 44.6%
??? [1] 42.6%
---------------------------------------------------------------------------------------
for-loop [35] 100.0%
[22] 1910(4.2%) 275(0.6%) random-gemstone ...lion-sorting-benchmark.rkt:14:0
random-ref [27] 58.9%
set [20] 26.7%
---------------------------------------------------------------------------------------
??? [8] 100.0%
[23] 3302(7.3%) 272(0.6%) ??? ...cts/racket/contract/private/list.rkt:209:10
for-loop [5] 91.7%
---------------------------------------------------------------------------------------
random-sample/out-replacement [25] 0.5%
sequence-generate* [52] 99.5%
[24] 41455(91.6%) 226(0.5%) make-sequence ...ects/racket/private/for.rkt:533:2
??? [37] 99.5%
---------------------------------------------------------------------------------------
random-ref [27] 100.0%
[25] 1010(2.2%) 214(0.5%) random-sample/out-replacement ...t/random.rkt:67:0
for-loop [18] 56.4%
make-sequence [24] 22.4%
---------------------------------------------------------------------------------------
successfully-got-the-right-kind-of-function [11]100.0%
[26] 233(0.5%) 174(0.4%) arity-checking-wrapper ...w-higher-order.rkt:428:0
matches-arity-exactly? [33] 25.5%
---------------------------------------------------------------------------------------
random-gemstone [22] 100.0%
[27] 1124(2.5%) 114(0.3%) random-ref ...v7.4/collects/racket/random.rkt:22:0
random-sample/out-replacement [25] 89.9%
---------------------------------------------------------------------------------------
set [20] 100.0%
[28] 114(0.3%) 114(0.3%) for-loop ...cts/racket/private/set-types.rkt:938:4
---------------------------------------------------------------------------------------
tree-trim-minimum [38] 100.0%
[29] 968(2.1%) 114(0.3%) for-loop ...on/private/transducer-sorting.rkt:79:7
??? [6] 70.0%
...higher-order.rkt:372:44 [21] 12.1%
??? [1] 6.2%
---------------------------------------------------------------------------------------
??? [37] 100.0%
[30] 41116(90.9%) 60(0.1%) make-initial-transducer-position ...ucer.rkt:100:0
sequence-generate* [52] 99.9%
---------------------------------------------------------------------------------------
??? [31] 50.0%
bottom-10/rebellion [47] 50.0%
[31] 60(0.1%) 60(0.1%) ??? .../contract/private/arrow-val-first.rkt:430:3
??? [31] 50.0%
---------------------------------------------------------------------------------------
??? [37] 6.3%
??? [53] 93.7%
[32] 1812(4.0%) 60(0.1%) transducer-position-try-emit ...ansducer.rkt:149:0
??? [3] 84.4%
??? [8] 12.3%
---------------------------------------------------------------------------------------
arity-checking-wrapper [26] 100.0%
[33] 60(0.1%) 60(0.1%) matches-arity-exactly? ...te/arrow-common.rkt:70:0
---------------------------------------------------------------------------------------
??? [8] 100.0%
[34] 503(1.1%) 54(0.1%) compare ...b/rebellion/private/comparator.rkt:49:0
??? [2] 89.4%
---------------------------------------------------------------------------------------
random-gems [46] 100.0%
[35] 1964(4.3%) 53(0.1%) for-loop ...n/rebellion-sorting-benchmark.rkt:19:2
random-gemstone [22] 97.3%
---------------------------------------------------------------------------------------
[36] 45238(100.0%) 0(0.0%) run-module-instance!125 (unknown source)
for-loop [39] 100.0%
---------------------------------------------------------------------------------------
make-sequence [24] 100.0%
[37] 41229(91.1%) 0(0.0%) ??? ...trib/rebellion/private/transducer.rkt:195:3
make-initial-transducer-position [30] 49.9%
transducer-position-advance-repeatedly [19] 49.4%
transducer-position-advance [7] 0.5%
transducer-position-try-emit [32] 0.1%
??? [8] 0.1%
---------------------------------------------------------------------------------------
??? [3] 100.0%
[38] 968(2.1%) 0(0.0%) tree-trim-minimum ...e/transducer-sorting.rkt:70:0
for-loop [29] 100.0%
---------------------------------------------------------------------------------------
run-module-instance!125 [36] 100.0%
[39] 45238(100.0%) 0(0.0%) for-loop (unknown source)
temp37_0 [40] 100.0%
---------------------------------------------------------------------------------------
for-loop [39] 100.0%
[40] 45238(100.0%) 0(0.0%) temp37_0 (unknown source)
[running body] [41] 100.0%
---------------------------------------------------------------------------------------
temp37_0 [40] 100.0%
[41] 45238(100.0%) 0(0.0%) [running body] ...sorting-benchmark.rkt" main):##f
profile-thunk16 [42] 100.0%
---------------------------------------------------------------------------------------
[running body] [41] 100.0%
[42] 45238(100.0%) 0(0.0%) profile-thunk16 ...e/pkgs/profile-lib/main.rkt:9:0
for-loop [43] 99.5%
---------------------------------------------------------------------------------------
profile-thunk16 [42] 100.0%
[43] 45002(99.5%) 0(0.0%) for-loop .../share/pkgs/profile-lib/main.rkt:39:16
temp9 [44] 100.0%
---------------------------------------------------------------------------------------
for-loop [43] 99.5%
[44] 45238(100.0%) 0(0.0%) temp9 ...lion/rebellion-sorting-benchmark.rkt:75:7
...ow-val-first.rkt:390:18 [45] 95.5%
random-gems [46] 4.3%
bottom-10/rebellion [47] 0.1%
---------------------------------------------------------------------------------------
temp9 [44] 100.0%
[45] 43215(95.5%) 0(0.0%) ...ow-val-first.rkt:390:18 (unknown source)
??? [8] 99.9%
??? [48] 0.1%
---------------------------------------------------------------------------------------
temp9 [44] 100.0%
[46] 1964(4.3%) 0(0.0%) random-gems ...ebellion-sorting-benchmark.rkt:18:0
for-loop [35] 100.0%
---------------------------------------------------------------------------------------
temp9 [44] 100.0%
[47] 60(0.1%) 0(0.0%) bottom-10/rebellion ...-sorting-benchmark.rkt:25:0
??? [31] 100.0%
---------------------------------------------------------------------------------------
...ow-val-first.rkt:390:18 [45] 100.0%
[48] 55(0.1%) 0(0.0%) ??? ...trib/rebellion/private/transducer.rkt:249:0
in-transduced [49] 100.0%
---------------------------------------------------------------------------------------
??? [48] 100.0%
[49] 55(0.1%) 0(0.0%) in-transduced ...lion/private/transducer.rkt:187:0
??? [8] 100.0%
---------------------------------------------------------------------------------------
??? [8] 100.0%
[50] 41398(91.5%) 0(0.0%) reduce-all .../rebellion/private/reducer.rkt:111:0
sequence-generate* [52] 99.6%
??? [53] 0.4%
---------------------------------------------------------------------------------------
??? [8] 100.0%
[51] 1762(3.9%) 0(0.0%) loop ...ontrib/rebellion/private/reducer.rkt:117:2
??? [53] 93.4%
??? [8] 6.6%
---------------------------------------------------------------------------------------
make-initial-transducer-position [30] 49.8%
reduce-all [50] 50.2%
[52] 41229(91.1%) 0(0.0%) sequence-generate* ...acket/private/for.rkt:1403:2
make-sequence [24] 100.0%
---------------------------------------------------------------------------------------
reduce-all [50] 5.8%
transducer-position-advance [7] 44.1%
loop [51] 50.1%
[53] 1928(4.3%) 0(0.0%) ??? ...7.4/collects/racket/private/for.rkt:1419:38
next-pos [54] 50.3%
transducer-position-try-emit [32] 49.7%
---------------------------------------------------------------------------------------
??? [53] 100.0%
[54] 1708(3.8%) 0(0.0%) next-pos ...rebellion/private/transducer.rkt:213:5
transducer-position-advance [7] 100.0%
---------------------------------------------------------------------------------------
Raw
rebellion-sorting-benchmark.rkt
#lang racket
(require math/number-theory
racket/random
rebellion/collection/entry
rebellion/collection/hash
rebellion/collection/list
rebellion/streaming/transducer
rebellion/type/record
rebellion/type/wrapper)
(define-record-type gemstone (kind weight))
(define (random-gemstone weight)
(gemstone #:kind (random-ref (set 'ruby 'sapphire 'emerald 'topaz))
#:weight (random 1 (add1 weight))))
(define (random-gems count)
(for/vector ([_ (in-range count)])
(random-gemstone count)))
(define (bottom-10/racket gems)
(take (sort (sequence->list gems) < #:key gemstone-weight) 10))
(define (bottom-10/rebellion gems)
(transduce gems
(sorting #:key gemstone-weight)
(taking 10)
#:into into-list))
(define-record-type timing-data (label cpu-time real-time gc-time))
(define (measure-runtime label thunk)
(define-values (_ cpu real gc) (time-apply thunk empty-list))
(timing-data #:label label #:cpu-time cpu #:real-time real #:gc-time gc))
(define (bottom-10-benchmark input-length)
(define gems (random-gems input-length))
(set (measure-runtime "Standard racket sort (milliseconds)"
(λ () (bottom-10/racket gems)))
(measure-runtime "Rebellion lazy sort (milliseconds)"
(λ () (bottom-10/rebellion gems)))))
(define-record-type stats (sum count max min average))
(define (single-datum-stats x)
(stats #:sum x #:count 1 #:max x #:min x #:average x))
(define (stats+ s p)
(define sum (+ (stats-sum s) (stats-sum p)))
(define count (+ (stats-count s) (stats-count p)))
(stats #:sum sum
#:count count
#:max (max (stats-max s) (stats-max p))
#:min (min (stats-min s) (stats-min p))
#:average (/ sum count)))
(define (run-benchmark benchmark #:size size #:iterations iterations)
(define timing-stats-by-label
(transduce (make-list iterations size)
(append-mapping benchmark)
(bisecting timing-data-label timing-data-cpu-time)
(mapping-values single-datum-stats)
#:into (combine-into-hash stats+)))
(transduce (in-hash-pairs timing-stats-by-label)
(bisecting car cdr)
#:into into-hash))
(module+ main
(require profile)
(match (current-command-line-arguments)
[(vector "profile")
(profile-thunk
(lambda ()
(void (bottom-10/rebellion (random-gems 1000))))
#:repeat 1000
#:order 'self)]
[(vector "benchmark")
(run-benchmark bottom-10-benchmark
#:size 1000
#:iterations 1000)]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment