Skip to content

Instantly share code, notes, and snippets.

@antimon2

antimon2/BitonicSorter.jl.ipynb

Last active August 20, 2022 07:45
Show Gist options
  • Save antimon2/1b20314ce0f196e9ed5226c9b2b84222 to your computer and use it in GitHub Desktop.
Save antimon2/1b20314ce0f196e9ed5226c9b2b84222 to your computer and use it in GitHub Desktop.
Download ZIP
BitonicSorter.jl
Display the source blob
Display the rendered blob
Raw
BitonicSorter.jl.ipynb
{
"cells": [
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.723Z",
"end_time": "2022-08-20T16:00:59.640000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "versioninfo()",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": "Julia Version 1.8.0\nCommit 5544a0fab76 (2022-08-17 13:38 UTC)\nPlatform Info:\n OS: Linux (x86_64-linux-gnu)\n CPU: 12 × Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz\n WORD_SIZE: 64\n LIBM: libopenlibm\n LLVM: libLLVM-13.0.1 (ORCJIT, skylake)\n Threads: 4 on 12 virtual cores\nEnvironment:\n JULIA_NUM_THREADS = 4\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.725Z",
"end_time": "2022-08-20T16:01:00.240000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "module BitonicSorterST\n\n# ref: https://en.wikipedia.org/wiki/Bitonic_sorter\n\nexport BitonicSort\n\nusing Base.Order: Ordering, lt\n\nstruct BitonicSortAlg <: Base.Sort.Algorithm end\nconst BitonicSort = BitonicSortAlg()\n\nfunction Base.sort!(x::AbstractVector, lo::Integer, hi::Integer, ::BitonicSortAlg, o::Ordering)\n lo ≥ hi && return x\n\n fullsize::Int = hi - lo\n d = sizeof(Int) * 8 - leading_zeros(fullsize - 1) # == ceil(Int, log(2, fullsize))\n\n for p = 1:d, q = 1:p\n _sort_kernel!(x, lo, hi, p, q, o)\n end\n return x\nend\n\nfunction _sort_kernel!(x::AbstractVector, lo, hi, p, q, o)\n # @assert p ≥ q\n halfsize_1 = Int(hi - lo) >> 0x01\n d = 1 << UInt(p - q)\n for s = 0:halfsize_1\n ioff = s & (d - 1)\n seg = lo + (s ⊻ ioff) << 0x01\n joff = q == 1 ? (2d - ioff - 1) : ioff + d\n i = seg + ioff\n j = seg + joff\n if !lt(o, x[i], x[j])\n x[i], x[j] = x[j], x[i]\n end\n end\nend\n\nend # module",
"execution_count": 2,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 2,
"data": {
"text/plain": "Main.BitonicSorterST"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.726Z",
"end_time": "2022-08-20T16:01:00.279000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "module BitonicSorterMT\n\nexport BitonicSortMT\n\nusing Base.Order: Ordering, lt\n\nstruct BitonicSortMTAlg <: Base.Sort.Algorithm end\nconst BitonicSortMT = BitonicSortMTAlg()\n\nfunction Base.sort!(x::AbstractVector, lo::Integer, hi::Integer, ::BitonicSortMTAlg, o::Ordering)\n lo ≥ hi && return x\n\n fullsize::Int = hi - lo\n d = sizeof(Int) * 8 - leading_zeros(fullsize - 1) # == ceil(Int, log(2, fullsize))\n\n for p = 1:d, q = 1:p\n _sort_kernel!(x, lo, hi, p, q, o)\n end\n return x\nend\n\nfunction _sort_kernel!(x::AbstractVector, lo, hi, p, q, o)\n # @assert p ≥ q\n halfsize_1 = (hi - lo) >> 0x01\n d = 1 << UInt(p - q)\n Threads.@threads for s = 0:halfsize_1\n ioff = s & (d - 1)\n seg = lo + (s ⊻ ioff) << 0x01\n joff = q == 1 ? (2d - ioff - 1) : ioff + d\n i = seg + ioff\n j = seg + joff\n if !lt(o, x[i], x[j])\n x[i], x[j] = x[j], x[i]\n end\n end\nend\n\nend # module",
"execution_count": 3,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 3,
"data": {
"text/plain": "Main.BitonicSorterMT"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.727Z",
"end_time": "2022-08-20T16:01:00.280000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using .BitonicSorterST",
"execution_count": 4,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.728Z",
"end_time": "2022-08-20T16:01:00.280000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using .BitonicSorterMT",
"execution_count": 5,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.730Z",
"end_time": "2022-08-20T16:01:01.288000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "x = [10, 30, 11, 20, 4, 330, 21, 110]",
"execution_count": 6,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 6,
"data": {
"text/plain": "8-element Vector{Int64}:\n 10\n 30\n 11\n 20\n 4\n 330\n 21\n 110"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.731Z",
"end_time": "2022-08-20T16:01:01.293000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "sort(x)",
"execution_count": 7,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 7,
"data": {
"text/plain": "8-element Vector{Int64}:\n 4\n 10\n 11\n 20\n 21\n 30\n 110\n 330"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.732Z",
"end_time": "2022-08-20T16:01:01.353000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "sort(x; alg=BitonicSort)",
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 8,
"data": {
"text/plain": "8-element Vector{Int64}:\n 4\n 10\n 11\n 20\n 21\n 30\n 110\n 330"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.733Z",
"end_time": "2022-08-20T16:01:01.453000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "sort(x; alg=BitonicSortMT)",
"execution_count": 9,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 9,
"data": {
"text/plain": "8-element Vector{Int64}:\n 4\n 10\n 11\n 20\n 21\n 30\n 110\n 330"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.735Z",
"end_time": "2022-08-20T16:01:01.458000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using BenchmarkTools",
"execution_count": 10,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.736Z",
"end_time": "2022-08-20T16:01:01.458000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using Random",
"execution_count": 11,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.737Z",
"end_time": "2022-08-20T16:01:15.498000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark sort!(x) setup=(x=rand(Float64, 2^16))",
"execution_count": 12,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 12,
"data": {
"text/plain": "BenchmarkTools.Trial: 1503 samples with 1 evaluation.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m3.015 ms\u001b[22m\u001b[39m … \u001b[35m 4.492 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 0.00%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m3.165 ms \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m3.237 ms\u001b[22m\u001b[39m ± \u001b[32m199.170 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m0.00% ± 0.00%\n\n \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▂\u001b[39m▇\u001b[39m█\u001b[39m█\u001b[34m▃\u001b[39m\u001b[39m▁\u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▄\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m▇\u001b[39m▇\u001b[32m▅\u001b[39m\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▃\n 3.01 ms\u001b[90m Histogram: frequency by time\u001b[39m 4.02 ms \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m0 bytes\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m0\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.738Z",
"end_time": "2022-08-20T16:01:26.436000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark sort!(x; alg=BitonicSort) setup=(x=rand(Float64, 2^16))",
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 13,
"data": {
"text/plain": "BenchmarkTools.Trial: 435 samples with 1 evaluation.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m10.681 ms\u001b[22m\u001b[39m … \u001b[35m 13.384 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 0.00%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m10.942 ms \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m11.394 ms\u001b[22m\u001b[39m ± \u001b[32m765.066 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m0.00% ± 0.00%\n\n \u001b[39m \u001b[39m \u001b[39m▂\u001b[39m█\u001b[39m▃\u001b[39m \u001b[39m \u001b[34m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▃\u001b[39m▅\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▇\u001b[39m▅\u001b[34m▄\u001b[39m\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[32m▃\u001b[39m\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▃\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▂\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▃\u001b[39m \u001b[39m▃\n 10.7 ms\u001b[90m Histogram: frequency by time\u001b[39m 13.1 ms \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m0 bytes\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m0\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.739Z",
"end_time": "2022-08-20T16:01:37.377000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark sort!(x; alg=BitonicSortMT) setup=(x=rand(Float64, 2^16))",
"execution_count": 14,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 14,
"data": {
"text/plain": "BenchmarkTools.Trial: 1060 samples with 1 evaluation.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m3.675 ms\u001b[22m\u001b[39m … \u001b[35m 6.807 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 26.52%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m4.294 ms \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m4.606 ms\u001b[22m\u001b[39m ± \u001b[32m721.825 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m0.04% ± 0.81%\n\n \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[39m▄\u001b[39m▄\u001b[39m▂\u001b[39m█\u001b[39m▃\u001b[39m \u001b[39m▂\u001b[39m \u001b[39m \u001b[39m \u001b[34m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▃\u001b[39m▄\u001b[39m▅\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[34m▆\u001b[39m\u001b[39m▄\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m▅\u001b[39m▄\u001b[32m▃\u001b[39m\u001b[39m▂\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▄\u001b[39m▂\u001b[39m▁\u001b[39m▃\u001b[39m▃\u001b[39m▄\u001b[39m▅\u001b[39m▄\u001b[39m▅\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▅\u001b[39m▄\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▃\n 3.68 ms\u001b[90m Histogram: frequency by time\u001b[39m 6.16 ms \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m300.06 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m3414\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.740Z",
"end_time": "2022-08-20T16:01:48.577000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark sort!(x) setup=(x=rand(Float32, 2^20))",
"execution_count": 15,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 15,
"data": {
"text/plain": "BenchmarkTools.Trial: 79 samples with 1 evaluation.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m61.248 ms\u001b[22m\u001b[39m … \u001b[35m 64.324 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 0.00%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m63.163 ms \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m63.012 ms\u001b[22m\u001b[39m ± \u001b[32m770.327 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m0.00% ± 0.00%\n\n \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m█\u001b[32m▄\u001b[39m\u001b[39m▄\u001b[34m \u001b[39m\u001b[39m▁\u001b[39m▄\u001b[39m \u001b[39m█\u001b[39m▁\u001b[39m \u001b[39m▁\u001b[39m▄\u001b[39m▁\u001b[39m▄\u001b[39m▄\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m█\u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m▆\u001b[39m█\u001b[39m▁\u001b[39m▆\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m█\u001b[32m█\u001b[39m\u001b[39m█\u001b[34m▁\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▁\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m█\u001b[39m▁\u001b[39m█\u001b[39m▁\u001b[39m▆\u001b[39m█\u001b[39m▆\u001b[39m \u001b[39m▁\n 61.2 ms\u001b[90m Histogram: frequency by time\u001b[39m 64.2 ms \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m0 bytes\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m0\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.741Z",
"end_time": "2022-08-20T16:02:00.963000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark sort!(x; alg=BitonicSort) setup=(x=rand(Float32, 2^20))",
"execution_count": 16,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 16,
"data": {
"text/plain": "BenchmarkTools.Trial: 17 samples with 1 evaluation.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m295.580 ms\u001b[22m\u001b[39m … \u001b[35m307.671 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 0.00%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m299.401 ms \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m299.821 ms\u001b[22m\u001b[39m ± \u001b[32m 3.975 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m0.00% ± 0.00%\n\n \u001b[39m█\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[34m \u001b[39m\u001b[39m█\u001b[39m \u001b[32m▁\u001b[39m\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m▁\u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m█\u001b[39m \u001b[39m \n \u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[34m▁\u001b[39m\u001b[39m█\u001b[39m▁\u001b[32m█\u001b[39m\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m \u001b[39m▁\n 296 ms\u001b[90m Histogram: frequency by time\u001b[39m 308 ms \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m0 bytes\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m0\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2022-08-20T07:00:58.742Z",
"end_time": "2022-08-20T16:02:12.340000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark sort!(x; alg=BitonicSortMT) setup=(x=rand(Float32, 2^20))",
"execution_count": 17,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 17,
"data": {
"text/plain": "BenchmarkTools.Trial: 57 samples with 1 evaluation.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m76.903 ms\u001b[22m\u001b[39m … \u001b[35m117.430 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 0.00%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m84.870 ms \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m88.659 ms\u001b[22m\u001b[39m ± \u001b[32m 10.616 ms\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m0.00% ± 0.00%\n\n \u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m \u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▁\u001b[39m \u001b[39m \u001b[34m \u001b[39m\u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[32m▄\u001b[39m\u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[34m▆\u001b[39m\u001b[39m█\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m█\u001b[39m█\u001b[39m█\u001b[32m█\u001b[39m\u001b[39m▁\u001b[39m█\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▆\u001b[39m▁\u001b[39m▁\u001b[39m▆\u001b[39m▁\u001b[39m▆\u001b[39m \u001b[39m▁\n 76.9 ms\u001b[90m Histogram: frequency by time\u001b[39m 112 ms \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m467.22 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m5397\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"kernelspec": {
"name": "julia-(4-threads)-1.8",
"display_name": "Julia (4 threads) 1.8.0",
"language": "julia"
},
"language_info": {
"file_extension": ".jl",
"name": "julia",
"mimetype": "application/julia",
"version": "1.8.0"
},
"gist": {
"id": "",
"data": {
"description": "BitonicSorter.jl",
"public": true
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Raw
postBuild
#!/bin/bash
julia -e 'using IJulia; IJulia.installkernel("Julia (4 threads)", "--project=@.", env=Dict("JULIA_NUM_THREADS"=>"4"))'
Raw
Project.toml
[compat]
julia = "1.6"
[deps]
BenchmarkTools = "6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment