Add minimum comparison element search function to array module

[ArtemkaKun]

Describe the feature

By @dumblob

Btw. for non-static arrays of fixed-sized items (e.g. integers, floats, all structs, fixed-length strings, etc.) there are also nice trivial optimizations possible like the limit branching in a tight loop by halving the number of comparisons (works also for tiny arrays). This should be a no-brainer.

Use Case

A faster search of an element in an array.

Proposed Solution

Example implementation

fn search(mut arr []int, x int) bool {
	arr_len := arr.len
	arr_len_minus := arr_len - 1
 
	if arr[arr_len_minus] == x {
		return true
	}
 
	backup := arr[arr_len_minus]
	arr[arr_len_minus] = x
 
	mut i := 0
 
	for {
		if arr[i] == x {
			arr[arr_len_minus] = backup
 
			if i < arr_len_minus {
				return true
			}
 
			return false
		}
 
		i += 1
	}
	return false
}

Other Information

Interesting concept, but unfortunately:

• it can't be applied everywhere, because in V this implementation requires mut array. If array is not mut - a new clone of the array must be created, which will eat all optimizations we did in the searching algorithm (I suppose).
• for me, this algorithm is 2 times slower in development build (for a big 100000 elements array, a small array is untested).

In the production build (Clang), the new algorithm is faster on about 17% which can be handy.

If you want to review/retest my code, here it is -> https://pastebin.com/mvRLWNYs

╭─yuart@yuart in ~/Projects via V v0.3.4 took 10s
╰─λ v run test.v
true
SPENT     0.213 ms in in
true
SPENT     0.449 ms in small comp

╭─yuart@yuart in ~/Projects via V v0.3.4 took 304ms
╰─λ v run test.v
true
SPENT     0.212 ms in in
true
SPENT     0.453 ms in small comp

╭─yuart@yuart in ~/Projects via V v0.3.4 took 304ms
╰─λ v run test.v
true
SPENT     0.215 ms in in
true
SPENT     0.465 ms in small comp

╭─yuart@yuart in ~/Projects via V v0.3.4 took 307ms
╰─λ v -cc clang -prod run test.v
Note: building an optimized binary takes much longer. It shouldn't be used with `v run`.
Use `v run` without optimization, or build an optimized binary with -prod first, then run it separately.
true
SPENT     0.023 ms in in
true
SPENT     0.019 ms in small comp

╭─yuart@yuart in ~/Projects via V v0.3.4 took 4s
╰─λ v -cc clang -prod run test.v
Note: building an optimized binary takes much longer. It shouldn't be used with `v run`.
Use `v run` without optimization, or build an optimized binary with -prod first, then run it separately.
true
SPENT     0.023 ms in in
true
SPENT     0.018 ms in small comp

╭─yuart@yuart in ~/Projects via V v0.3.4 took 4s
╰─λ v -cc clang -prod run test.v
Note: building an optimized binary takes much longer. It shouldn't be used with `v run`.
Use `v run` without optimization, or build an optimized binary with -prod first, then run it separately.
true
SPENT     0.023 ms in in
true
SPENT     0.019 ms in small comp

Acknowledgements

• I may be able to implement this feature request
• This feature might incur a breaking change

Version used

V 0.3.4 e2f18fc.bc88183

Environment details (OS name and version, etc.)

V full version: V 0.3.4 e2f18fc.bc88183
OS: linux, "Garuda Linux"
Processor: 16 cpus, 64bit, little endian, AMD Ryzen 7 3800X 8-Core Processor

getwd: /home/yuart
vexe: /home/yuart/Projects/v/v
vexe mtime: 2023-05-25 09:39:56

vroot: OK, value: /home/yuart/Projects/v
VMODULES: OK, value: /home/yuart/.vmodules
VTMP: OK, value: /tmp/v_1000

Git version: git version 2.40.1
Git vroot status: weekly.2023.19-67-gbc881833 (8 commit(s) behind V master)
.git/config present: true

CC version: cc (GCC) 13.1.1 20230429
thirdparty/tcc status: thirdparty-linux-amd64 12f392c3

[JalonSolov]

How well does it work on arrays with multiple identical values?

[ArtemkaKun]

Benchmark was done on array of random ints with a lot of duplications. So you can see results above

[dumblob]

Another option would be to skip all the boilerplate with backup as it adds too much branching for my liking 😉 and instead just instruct the memory allocator to preallocate one more place. But I did not try nor measure it.

Yes, it is a minuscule waste of memory (always one item), but:

a) V arrays are huge under the hood - making them one item bigger is no big deal.
b) We are used to wasting one last element from C already anyway 😉.