mirror of
https://github.com/emirpasic/gods.git
synced 2026-06-26 17:56:21 +03:00
Kashiwa
454720c27e
* Improved ArrayList performance by removing `size` field.
Removed the `size` field from the `List` struct and replaced it with the built-in Go slice length implementation.
+ Achieved an average reduction of nearly 40% in execution time for `ArrayListGet`.
+ Achieved an average reduction of nearly 23% in memory usage for `ArrayListAdd`.
+ However, this change slightly increased the execution time for `ArrayListAdd` by 2.7%.
```
goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/v2/lists/arraylist
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
│ old.txt │ new.txt │
│ sec/op │ sec/op vs base │
ArrayListGet100-8 51.20n ± 0% 32.49n ± 0% -36.53% (n=50)
ArrayListGet1000-8 447.5n ± 0% 270.3n ± 1% -39.60% (n=50)
ArrayListGet10000-8 4.418µ ± 1% 2.540µ ± 0% -42.52% (n=50)
ArrayListGet100000-8 44.06µ ± 0% 25.15µ ± 0% -42.91% (n=50)
ArrayListAdd100-8 726.5n ± 1% 760.5n ± 0% +4.69% (p=0.000 n=50)
ArrayListAdd1000-8 7.437µ ± 2% 7.389µ ± 1% ~ (p=0.746 n=50)
ArrayListAdd10000-8 70.06µ ± 1% 74.34µ ± 1% +6.11% (p=0.000 n=50)
ArrayListAdd100000-8 740.2µ ± 1% 728.9µ ± 2% ~ (p=0.147 n=50)
ArrayListRemove100-8 233.8n ± 0% 233.9n ± 0% ~ (p=0.162 n=50)
ArrayListRemove1000-8 2.275µ ± 0% 2.276µ ± 0% ~ (p=0.452 n=50)
ArrayListRemove10000-8 22.75µ ± 0% 22.75µ ± 0% ~ (p=0.956 n=50)
ArrayListRemove100000-8 1.323m ± 1% 1.331m ± 1% ~ (p=0.120 n=50)
geomean 7.218µ 6.119µ -15.22%
│ old.txt │ new.txt │
│ B/op │ B/op vs base │
ArrayListGet100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd100-8 2.987Ki ± 0% 2.087Ki ± 1% -30.14% (n=50)
ArrayListAdd1000-8 27.50Ki ± 1% 23.31Ki ± 2% -15.24% (p=0.000 n=50)
ArrayListAdd10000-8 293.9Ki ± 1% 204.7Ki ± 1% -30.36% (n=50)
ArrayListAdd100000-8 2.667Mi ± 1% 2.244Mi ± 12% -15.86% (p=0.000 n=50)
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove100000-8 453.5 ± 1% 457.5 ± 1% ~ (p=0.059 n=50)
geomean ² -8.38% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
│ old.txt │ new.txt │
│ allocs/op │ allocs/op vs base │
ArrayListGet100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
geomean ² +0.00% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
```
* Improve ArrayList Remove() by `slices.Delete`
The performance of `slices.Delete()` is better
```
goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/v2/lists/arraylist
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
│ old-remove.txt │ new-remove.txt │
│ sec/op │ sec/op vs base │
ArrayListRemove100-8 234.2n ± 1% 211.2n ± 2% -9.82% (p=0.000 n=10)
ArrayListRemove1000-8 2.293µ ± 1% 2.063µ ± 4% -10.05% (p=0.000 n=10)
ArrayListRemove10000-8 22.78µ ± 1% 20.53µ ± 2% -9.86% (p=0.000 n=10)
ArrayListRemove100000-8 1.318m ± 3% 1.279m ± 2% -2.96% (p=0.019 n=10)
geomean 11.27µ 10.34µ -8.22%
│ old-remove.txt │ new-remove.txt │
│ B/op │ B/op vs base │
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove100000-8 452.0 ± 4% 444.5 ± 1% ~ (p=0.224 n=10)
geomean ² -0.42% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
│ old-remove.txt │ new-remove.txt │
│ allocs/op │ allocs/op vs base │
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
geomean ² +0.00% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
```
* Improve ArrayList Clear() by using built-in clear() instead of creating a new one
* Refactor code by `slices` package.
* Refactor ArrayList Insert() by `slices.Insert()`