-
Notifications
You must be signed in to change notification settings - Fork 0
/
results.txt
126 lines (93 loc) · 4.91 KB
/
results.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
Sets
# 63 schedules
HASHSET_LIMITS_1 = -kind=set -hashKind=ident -valueBound=2 -nthread=1..2 \
-nstep=1..2 -npreAdd=0 -threadSym -checkTermination -ncore=$(NCORE)
# 63 schedules
HASHSET_LIMITS_1ND = -kind=set -hashKind=nd -hashRangeBound=2 -hashDomainBound=2 \
-valueBound=2 -nthread=1..2 -nstep=1..2 -npreAdd=0 -threadSym -checkTermination \
-ncore=$(NCORE)
# 63 schedules
HASHSET_LIMITS_1.5ND = -kind=set -hashKind=nd -hashRangeBound=2 -hashDomainBound=3 \
-valueBound=3 -nthread=1..3 -nstep=1..3 -npreAdd=0 -threadSym \
-checkTermination -ncore=$(NCORE)
# 1758 schedules
HASHSET_LIMITS_2 = -kind=set -hashKind=ident -valueBound=3 -nthread=1..3 \
-nstep=1..3 -npreAdd=0 -threadSym -checkTermination -ncore=$(NCORE)
# 1758 schedules
HASHSET_LIMITS_2ND = -kind=set -hashKind=nd -hashRangeBound=4 -hashDomainBound=3 \
-valueBound=3 -nthread=1..3 -nstep=1..3 -npreAdd=0 -threadSym -checkTermination \
-ncore=$(NCORE)
# 5274 schedules:
HASHSET_LIMITS_3 = -kind=set -hashKind=ident -valueBound=3 -nthread=1..3 \
-nstep=1..3 -npreAdd=1..3 -threadSym -checkTermination -ncore=$(NCORE)
# 3645 schedules:
HASHSET_LIMITS_4 = -kind=set -hashKind=ident -valueBound=3 -nthread=3 \
-nstep=4 -npreAdd=0 -threadSym -checkTermination -ncore=$(NCORE)
On MabBookPro (4 threads): time in seconds
1 2 3 4 1ND 1.5ND 2ND S1 S2
--------------------------------------------------------
CoarseHashSet......... 15 324 954 17427 15 736 3593 14 162
StripedHashSet.........15 347 1064 18127 16 899 4338 15 170
StripedCuckooHashSet...16 394 566* 22460 22 infty ---- 57 269
* Early finish due to finding out of bounds error in relocate method
Lists
# 63 schedules
LIST_LIMITS_1 = -kind=set -hashKind=ident -valueBound=2 -nthread=1..2 \
-nstep=1..2 -npreAdd=0 -threadSym -checkTermination -ncore=$(NCORE)
# 1758 schedules
LIST_LIMITS_2 = -kind=set -hashKind=ident -valueBound=3 -nthread=1..3 \
-nstep=1..3 -npreAdd=0 -threadSym -checkTermination -ncore=$(NCORE)
# 5274 schedules: approx 15 minutes on Mac
LIST_LIMITS_3 = -kind=set -hashKind=ident -valueBound=3 -nthread=1..3 \
-nstep=1..3 -npreAdd=1..3 -threadSym -checkTermination -ncore=$(NCORE)
# 3645 schedules: estimate 5 hours on Mac
LIST_LIMITS_4 = -kind=set -hashKind=ident -valueBound=3 -nthread=3 \
-nstep=4 -npreAdd=0 -threadSym -checkTermination -ncore=$(NCORE)
Mac (4 threads): time in seconds
1 2 3 4 S1 S2
------------------------------------
CoarseList.......... 14 290 915 14111 13 123
FineList............ 14 305 1069 17755 18 137
OptimisticList...... 14 365 1295 23211 27 239
LazyList............ 13 347 1168 23771 23 236
LockFreeList........ 15 348 1381 23174 29 247
LockFreeListOriginal 15 201* 364* 3917* 29 243
* Early finish due to finding sequential consistency violation
Queues
# 25 schedules
QUEUE_LIMITS_1 = -kind=queue -genericVals -threadSym -nthread=1..2 \
-nstep=1..3 -npreAdd=0 -checkTermination -ncore=$(NCORE)
# 58 schedules
QUEUE_LIMITS_2 = -kind=queue -genericVals -threadSym -nthread=1..3 \
-nstep=1..3 -npreAdd=0..1 -checkTermination -ncore=$(NCORE)
# 249 schedules
QUEUE_LIMITS_3 = -kind=queue -genericVals -threadSym -nthread=1..3 \
-nstep=1..4 -npreAdd=0..2 -checkTermination -ncore=$(NCORE)
Mac (4 threads): time in seconds
1 2 3 S1 S2
--------------------------
UnboundedQueue....... 8 20 441 13 380
LockFreeQueue........ 9 33 1078 19 1417
Priority Queues
# 7 schedules
PQUEUE_LIMITS_1 = -kind=pqueue -genericVals -threadSym -nthread=1..2 \
-nstep=1..2 -npreAdd=0 -distinctPriorities -addsDominate -ncore=$(NCORE)
# 33 schedules
PQUEUE_LIMITS_2 = -kind=pqueue -genericVals -threadSym -nthread=1..3 \
-nstep=1..3 -npreAdd=0 -distinctPriorities -addsDominate -ncore=$(NCORE)
# 3467 schedules
PQUEUE_LIMITS_3 = -kind=pqueue -genericVals -threadSym -nthread=1..3 \
-nstep=1..3 -npreAdd=1..3 -distinctPriorities -addsDominate -ncore=$(NCORE)
Mac (4 threads): time in seconds
1 2 3 S1 S2
-------------------------------
FineGrainedHeap........ 4* 7* 222* 3+ 3+
FineGrainedHeapNoCycles 4 13+ 228+ 3+ 3+
FineGrainedHeapFair.... 5 16+ 235+ 3+ 4+
SkipQueue.............. 10 1172 432x 288x OOM
SkipQueuePatched....... 9 1109 OOM 2036! ????
SkipQueuePatchedS1: 2356s, defect detected
* = early stop due to finding cycle violation in add
+ = early stop due to finding deadlock violation between add and removeMin
x = early stop due to finding cycle violation in findAndMarkMin
! = early stop due to finding sequential consistency violation