Skip to content

Instantly share code, notes, and snippets.

@antimon2

antimon2/ThreadSafeDicts.jl.ipynb

Last active November 12, 2020 13:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save antimon2/1ce455916a49888a32016169e09418a1 to your computer and use it in GitHub Desktop.
Save antimon2/1ce455916a49888a32016169e09418a1 to your computer and use it in GitHub Desktop.
Download ZIP
ThreadSafeDict/ThreadSafeDicts.jl
Display the source blob
Display the rendered blob
Raw
ThreadSafeDicts.jl.ipynb
{
"cells": [
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:21.458Z",
"end_time": "2020-11-12T21:40:24.340000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "versioninfo()",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": "Julia Version 1.5.3\nCommit 788b2c77c1 (2020-11-09 13:37 UTC)\nPlatform Info:\n OS: Linux (x86_64-pc-linux-gnu)\n CPU: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz\n WORD_SIZE: 64\n LIBM: libopenlibm\n LLVM: libLLVM-9.0.1 (ORCJIT, skylake)\nEnvironment:\n JULIA_NUM_THREADS = 4\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:26.736Z",
"end_time": "2020-11-12T21:40:26.359000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using Base.Threads\nusing Base: AbstractLock, Callable",
"execution_count": 2,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:27.778Z",
"end_time": "2020-11-12T21:40:27.406000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "mutable struct ThreadSafeDict{K,V,L<:AbstractLock} <: AbstractDict{K,V}\n dict::Dict{K,V}\n lock::L\n ThreadSafeDict{K,V}() where {K,V} = \n new{K,V,ReentrantLock}(Dict{K,V}(), ReentrantLock())\n ThreadSafeDict{K,V,L}() where {K,V,L<:AbstractLock} = \n new{K,V,L}(Dict{K,V}(), L())\nend",
"execution_count": 3,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:28.353Z",
"end_time": "2020-11-12T21:40:27.982000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.iterate(d::ThreadSafeDict, state...) = iterate(d.dict, state...)\nBase.length(d::ThreadSafeDict) = length(d.dict)\nBase.isempty(d::ThreadSafeDict) = isempty(d.dict)",
"execution_count": 4,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:29.011Z",
"end_time": "2020-11-12T21:40:28.637000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.sizehint!(d::ThreadSafeDict, n::Integer)\n lock(d.lock) do\n sizehint!(d.dict, n)\n end\n return d\nend",
"execution_count": 5,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:29.884Z",
"end_time": "2020-11-12T21:40:29.508000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "_unsafe_haskey(d::ThreadSafeDict, key) = haskey(d.dict, key)\nfunction Base.haskey(d::ThreadSafeDict, key)\n lock(d.lock) do\n _unsafe_haskey(d, key)\n end\nend",
"execution_count": 6,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:39.644Z",
"end_time": "2020-11-12T21:40:39.271000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.get(d::ThreadSafeDict, key, default)\n lock(d.lock) do\n if _unsafe_haskey(d, key)\n _unsafe_getindex(d, key)\n else\n default\n end\n end\nend\n\nfunction Base.get(default::Base.Callable, d::ThreadSafeDict, key)\n lock(d.lock) do\n if _unsafe_haskey(d, key)\n _unsafe_getindex(d, key)\n else\n default()\n end\n end\nend",
"execution_count": 7,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:40.886Z",
"end_time": "2020-11-12T21:40:40.520000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.get!(d::ThreadSafeDict, key, default)\n lock(d.lock) do\n if _unsafe_haskey(d, key)\n _unsafe_getindex(d, key)\n else\n v = default\n _unsafe_addindex!(d, v, key)\n v\n end\n end\nend\n\nfunction Base.get!(default::Callable, d::ThreadSafeDict, key)\n lock(d.lock) do\n if _unsafe_haskey(d, key)\n _unsafe_getindex(d, key)\n else\n v = default()\n _unsafe_addindex!(d, v, key)\n v\n end\n end\nend",
"execution_count": 8,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:42.068Z",
"end_time": "2020-11-12T21:40:41.691000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "_unsafe_getindex(d::ThreadSafeDict, key) = d.dict[key]\nfunction Base.getindex(d::ThreadSafeDict, key)\n lock(d.lock) do\n if _unsafe_haskey(d, key)\n _unsafe_getindex(d, key)\n else\n throw(KeyError(key))\n end\n end\nend",
"execution_count": 9,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:42.756Z",
"end_time": "2020-11-12T21:40:42.380000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function _unsafe_addindex!(d::ThreadSafeDict, v, key)\n d.dict[key] = v\nend\nfunction Base.setindex!(d::ThreadSafeDict, v, key)\n lock(d.lock) do\n _unsafe_addindex!(d, v, key)\n end\n d\nend",
"execution_count": 10,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:43.373Z",
"end_time": "2020-11-12T21:40:43.003000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.delete!(d::ThreadSafeDict, key)\n lock(d.lock) do\n delete!(d.dict, key)\n end\n d\nend\nfunction Base.pop!(d::ThreadSafeDict, key)\n lock(d.lock) do\n pop!(d.dict, key)\n end\nend",
"execution_count": 11,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:43.658Z",
"end_time": "2020-11-12T21:40:43.283000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.empty!(d::ThreadSafeDict)\n lock(d.lock) do\n empty!(d.dict)\n end\n d\nend",
"execution_count": 12,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 実験"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:47.197Z",
"end_time": "2020-11-12T21:40:47.738000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using Random\np = randperm(10)",
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 13,
"data": {
"text/plain": "10-element Array{Int64,1}:\n 2\n 9\n 1\n 8\n 5\n 7\n 10\n 3\n 6\n 4"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:53.510Z",
"end_time": "2020-11-12T21:40:53.403000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "f!(d, n) = get!(d, n) do\n println(\"recursive $(n)->$(n-1) (threadid: $(threadid()))\")\n v, _i = f!(d, n-1)\n (v + 1, threadid())\nend",
"execution_count": 14,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 14,
"data": {
"text/plain": "f! (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### Thread-Unsafe"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:55.663Z",
"end_time": "2020-11-12T21:40:55.819000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "d0 = Dict{Int,Tuple{Int,Int}}()",
"execution_count": 15,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 15,
"data": {
"text/plain": "Dict{Int64,Tuple{Int64,Int64}}()"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:40:59.307Z",
"end_time": "2020-11-12T21:40:59.143000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "d0[1] = (1, 1)",
"execution_count": 16,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 16,
"data": {
"text/plain": "(1, 1)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:41:00.290Z",
"end_time": "2020-11-12T21:41:00.039000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@threads for i = 1:10\n f!(d0, p[i])\nend",
"execution_count": 17,
"outputs": [
{
"output_type": "stream",
"text": "recursive 10->9 (threadid: 3)\nrecursive 6->5 (threadid: 4)\nrecursive 9->8 (threadid: 3)\nrecursive 5->4 (threadid: 4)\nrecursive 8->7 (threadid: 2)\nrecursive 4->3 (threadid: 4)\nrecursive 8->7 (threadid: 3)\nrecursive 7->6 (threadid: 2)\nrecursive 7->6 (threadid: 3)\nrecursive 6->5 (threadid: 2)\nrecursive 3->2 (threadid: 4)\nrecursive 5->4 (threadid: 2)\nrecursive 2->1 (threadid: 4)\nrecursive 2->1 (threadid: 1)\nrecursive 4->3 (threadid: 2)\nrecursive 6->5 (threadid: 3)\nrecursive 9->8 (threadid: 1)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:41:03.556Z",
"end_time": "2020-11-12T21:41:03.232000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "d0",
"execution_count": 18,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 18,
"data": {
"text/plain": "Dict{Int64,Tuple{Int64,Int64}} with 10 entries:\n 7 => (7, 3)\n 4 => (4, 2)\n 9 => (9, 1)\n 10 => (10, 3)\n 2 => (2, 1)\n 3 => (3, 4)\n 5 => (5, 2)\n 8 => (8, 3)\n 6 => (6, 3)\n 1 => (1, 1)"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### Thread-Safe"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2020-11-12T12:41:05.239Z",
"end_time": "2020-11-12T21:41:05.260000+09:00"
}
},
"cell_type": "code",
"source": "d1 = ThreadSafeDict{Int,Tuple{Int,Int}}()",
"execution_count": 19,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 19,
"data": {
"text/plain": "ThreadSafeDict{Int64,Tuple{Int64,Int64},ReentrantLock}()"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:41:06.260Z",
"end_time": "2020-11-12T21:41:05.921000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "d1[1] = (1, 1)",
"execution_count": 20,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 20,
"data": {
"text/plain": "(1, 1)"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2020-11-12T12:41:07.317Z",
"end_time": "2020-11-12T21:41:07.023000+09:00"
}
},
"cell_type": "code",
"source": "@threads for i = 1:10\n f!(d1, p[i])\nend",
"execution_count": 21,
"outputs": [
{
"output_type": "stream",
"text": "recursive 6->5 (threadid: 4)\nrecursive 5->4 (threadid: 4)\nrecursive 4->3 (threadid: 4)\nrecursive 3->2 (threadid: 4)\nrecursive 2->1 (threadid: 4)\nrecursive 8->7 (threadid: 2)\nrecursive 7->6 (threadid: 2)\nrecursive 10->9 (threadid: 3)\nrecursive 9->8 (threadid: 3)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2020-11-12T12:41:09.058Z",
"end_time": "2020-11-12T21:41:08.681000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "d1",
"execution_count": 22,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 22,
"data": {
"text/plain": "ThreadSafeDict{Int64,Tuple{Int64,Int64},ReentrantLock} with 10 entries:\n 7 => (7, 2)\n 4 => (4, 4)\n 9 => (9, 3)\n 10 => (10, 3)\n 2 => (2, 4)\n 3 => (3, 4)\n 5 => (5, 4)\n 8 => (8, 2)\n 6 => (6, 4)\n 1 => (1, 1)"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"kernelspec": {
"name": "julia-(4-threads)-1.5",
"display_name": "Julia (4 threads) 1.5.3",
"language": "julia"
},
"language_info": {
"file_extension": ".jl",
"name": "julia",
"mimetype": "application/julia",
"version": "1.5.3"
},
"gist": {
"id": "",
"data": {
"description": "ThreadSafeDict/ThreadSafeDicts.jl",
"public": true
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment