Grcov report - budmap.rs

1

use std::{collections::HashMap, hash::BuildHasher};

2

3

use budlang::vm::budmap::BudMap;

4

use criterion::{

5

    criterion_group, criterion_main, measurement::WallTime, BatchSize, BenchmarkGroup, BenchmarkId,

6

    Criterion,

7

};

8

use indexmap::IndexMap;

9

10

trait Map<S>: Clone {

11

    fn label() -> &'static str;

12

    fn with_hasher(hasher: S) -> Self;

13

    fn insert(&mut self, key: u32, value: u32) -> Option<u32>;

14

    fn get(&self, key: &u32) -> Option<&u32>;

15

    fn remove(&mut self, key: &u32) -> Option<u32>;

16

17

18

impl<S> Map<S> for HashMap<u32, u32, S>

19

where

20

    S: BuildHasher + Clone,

21

22

30

    fn label() -> &'static str {

23

30

        "HashMap"

24

30

25

26

30

    fn with_hasher(hasher: S) -> Self {

27

30

        Self::with_hasher(hasher)

28

30

29

30

4999840

    fn insert(&mut self, key: u32, value: u32) -> Option<u32> {

31

4999840

        HashMap::insert(self, key, value)

32

4999840

33

34

10

    fn get(&self, key: &u32) -> Option<&u32> {

35

10

        HashMap::get(self, key)

36

10

37

38

10

    fn remove(&mut self, key: &u32) -> Option<u32> {

39

10

        HashMap::remove(self, key)

40

10

41

42

43

impl<S> Map<S> for BudMap<u32, u32, S>

44

where

45

    S: BuildHasher + Clone,

46

47

30

    fn label() -> &'static str {

48

30

        "BudMap"

49

30

50

51

30

    fn with_hasher(hasher: S) -> Self {

52

30

        Self::with_hasher(hasher)

53

30

54

55

4999840

    fn insert(&mut self, key: u32, value: u32) -> Option<u32> {

56

4999840

        BudMap::insert(self, key, value)

57

4999840

58

59

10

    fn get(&self, key: &u32) -> Option<&u32> {

60

10

        BudMap::get(self, key)

61

10

62

63

10

    fn remove(&mut self, key: &u32) -> Option<u32> {

64

10

        BudMap::remove(self, key)

65

10

66

67

68

impl<S> Map<S> for IndexMap<u32, u32, S>

69

where

70

    S: BuildHasher + Clone,

71

72

30

    fn label() -> &'static str {

73

30

        "IndexMap"

74

30

75

76

30

    fn with_hasher(hasher: S) -> Self {

77

30

        Self::with_hasher(hasher)

78

30

79

80

4999840

    fn insert(&mut self, key: u32, value: u32) -> Option<u32> {

81

4999840

        IndexMap::insert(self, key, value)

82

4999840

83

84

10

    fn get(&self, key: &u32) -> Option<&u32> {

85

10

        IndexMap::get(self, key)

86

10

87

88

10

    fn remove(&mut self, key: &u32) -> Option<u32> {

89

10

        IndexMap::remove(self, key)

90

10

91

92

93

30

fn fill_entries<M: Map<fnv::FnvBuildHasher>>(

94

30

    state: fnv::FnvBuildHasher,

95

30

    count: usize,

96

30

    bench: &mut BenchmarkGroup<'_, WallTime>,

97

30

) {

98

30

    let rng = fastrand::Rng::with_seed(0);

99

30

100

30

    bench.bench_function(BenchmarkId::new(M::label(), count), |b| {

101

30

        b.iter(|| {

102

30

            let mut map = M::with_hasher(state.clone());

103

4999830

            for _ in 0..count {

104

4999830

                let key = rng.u32(..);

105

4999830

                let value = rng.u32(..);

106

4999830

                map.insert(key, value);

107

4999830

108

30

});

109

30

});

110

30

111

112

10

fn bench_fills(

113

10

    state: &fnv::FnvBuildHasher,

114

10

    count: usize,

115

10

    bench: &mut BenchmarkGroup<'_, WallTime>,

116

10

) {

117

10

    fill_entries::<BudMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

118

10

    fill_entries::<HashMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

119

10

    fill_entries::<IndexMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

120

10

121

122

1

pub fn fills(c: &mut Criterion) {

123

1

    let state = fnv::FnvBuildHasher::default();

124

1

    let mut group = c.benchmark_group("fills");

125

1

    bench_fills(&state, 10, &mut group);

126

1

    bench_fills(&state, 100, &mut group);

127

1

    bench_fills(&state, 500, &mut group);

128

1

    bench_fills(&state, 1_000, &mut group);

129

1

    bench_fills(&state, 5_000, &mut group);

130

1

    bench_fills(&state, 10_000, &mut group);

131

1

    bench_fills(&state, 50_000, &mut group);

132

1

    bench_fills(&state, 100_000, &mut group);

133

1

    bench_fills(&state, 500_000, &mut group);

134

1

    bench_fills(&state, 1_000_000, &mut group);

135

1

136

137

30

fn remove_reinsert_entries<M: Map<fnv::FnvBuildHasher>>(

138

30

    state: fnv::FnvBuildHasher,

139

30

    count: usize,

140

30

    bench: &mut BenchmarkGroup<'_, WallTime>,

141

30

) {

142

30

    bench.bench_function(BenchmarkId::new(M::label(), count), |b| {

143

30

        let rng = fastrand::Rng::with_seed(0);

144

30

        let mut keys = Vec::with_capacity(count);

145

30

        let mut map = M::with_hasher(state.clone());

146

30

147

30

        for _ in 0..count {

148

4999830

            let key = rng.u32(..);

149

4999830

            let value = rng.u32(..);

150

4999830

            if map.insert(key, value).is_none() {

151

4999389

                keys.push(key);

152

4999389

153

154

155

30

        rng.shuffle(&mut keys);

156

30

157

30

        let mut key_index = 0;

158

30

        b.iter_batched(

159

30

            || {

160

30

                key_index += 1;

161

30

                if key_index == keys.len() {

162

                    key_index = 0;

163

30

164

30

                key_index

165

30

},

166

30

            |key_index| {

167

30

                let key = keys[key_index];

168

30

                let value = map.remove(&key).unwrap();

169

30

                map.insert(key, value);

170

30

},

171

30

            BatchSize::LargeInput,

172

30

);

173

30

});

174

30

175

176

10

fn bench_remove_reinserts(

177

10

    state: &fnv::FnvBuildHasher,

178

10

    count: usize,

179

10

    bench: &mut BenchmarkGroup<'_, WallTime>,

180

10

) {

181

10

    remove_reinsert_entries::<BudMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

182

10

    remove_reinsert_entries::<HashMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

183

10

    remove_reinsert_entries::<IndexMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

184

10

185

186

1

pub fn insert_removals(c: &mut Criterion) {

187

1

    let state = fnv::FnvBuildHasher::default();

188

1

    let mut group = c.benchmark_group("remove-reinsert");

189

1

    bench_remove_reinserts(&state, 10, &mut group);

190

1

    bench_remove_reinserts(&state, 100, &mut group);

191

1

    bench_remove_reinserts(&state, 500, &mut group);

192

1

    bench_remove_reinserts(&state, 1_000, &mut group);

193

1

    bench_remove_reinserts(&state, 5_000, &mut group);

194

1

    bench_remove_reinserts(&state, 10_000, &mut group);

195

1

    bench_remove_reinserts(&state, 50_000, &mut group);

196

1

    bench_remove_reinserts(&state, 100_000, &mut group);

197

1

    bench_remove_reinserts(&state, 500_000, &mut group);

198

1

    bench_remove_reinserts(&state, 1_000_000, &mut group);

199

1

200

201

30

fn get_entries<M: Map<fnv::FnvBuildHasher>>(

202

30

    state: fnv::FnvBuildHasher,

203

30

    count: usize,

204

30

    bench: &mut BenchmarkGroup<'_, WallTime>,

205

30

) {

206

30

    bench.bench_function(BenchmarkId::new(M::label(), count), |b| {

207

30

        let rng = fastrand::Rng::with_seed(0);

208

30

        let mut keys = Vec::with_capacity(count);

209

30

        let mut map = M::with_hasher(state.clone());

210

30

211

4999830

        for _ in 0..count {

212

4999830

            let key = rng.u32(..);

213

4999830

            let value = rng.u32(..);

214

4999830

            map.insert(key, value);

215

4999830

            keys.push(key);

216

4999830

217

218

30

        rng.shuffle(&mut keys);

219

30

220

30

        let mut key_index = 0;

221

30

        b.iter_batched(

222

30

            || {

223

30

                key_index += 1;

224

30

                if key_index == keys.len() {

225

                    key_index = 0;

226

30

227

30

                key_index

228

30

},

229

30

            |key_index| {

230

30

                map.get(&keys[key_index]).unwrap();

231

30

},

232

30

            BatchSize::SmallInput,

233

30

);

234

30

});

235

30

236

237

10

fn bench_gets(state: &fnv::FnvBuildHasher, count: usize, bench: &mut BenchmarkGroup<'_, WallTime>) {

238

10

    get_entries::<BudMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

239

10

    get_entries::<HashMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

240

10

    get_entries::<IndexMap<u32, u32, fnv::FnvBuildHasher>>(state.clone(), count, bench);

241

10

242

243

1

pub fn gets(c: &mut Criterion) {

244

1

    let state = fnv::FnvBuildHasher::default();

245

1

    let mut group = c.benchmark_group("gets");

246

1

    bench_gets(&state, 10, &mut group);

247

1

    bench_gets(&state, 100, &mut group);

248

1

    bench_gets(&state, 500, &mut group);

249

1

    bench_gets(&state, 1_000, &mut group);

250

1

    bench_gets(&state, 5_000, &mut group);

251

1

    bench_gets(&state, 10_000, &mut group);

252

1

    bench_gets(&state, 50_000, &mut group);

253

1

    bench_gets(&state, 100_000, &mut group);

254

1

    bench_gets(&state, 500_000, &mut group);

255

1

    bench_gets(&state, 1_000_000, &mut group);

256

1

257

258

1

pub fn benchmarks(c: &mut Criterion) {

259

1

    fills(c);

260

1

    insert_removals(c);

261

1

    gets(c);

262

1

263

264

criterion_group!(benches, benchmarks);

265

criterion_main!(benches);