Chunk: memory safety

[samber]

Currently, the slices returned by lo.Chunk share the same memory space that the collection sent to the helper.

It seems not very safe to me. I open this issue to discuss about an improvement of lo.Chunk. Using copy() would be slower, and consume more memory, but much safer.

Discussion started here: #491

BenchmarkChunk
BenchmarkChunk/strings_10
BenchmarkChunk/strings_10-12            14886344            80.03 ns/op
BenchmarkChunk/strings_100
BenchmarkChunk/strings_100-12            1814036           660.8 ns/op
BenchmarkChunk/strings_1000
BenchmarkChunk/strings_1000-12            183382          6143 ns/op
BenchmarkChunk/ints10
BenchmarkChunk/ints10-12                20346310            57.41 ns/op
BenchmarkChunk/ints100
BenchmarkChunk/ints100-12                2672658           433.6 ns/op
BenchmarkChunk/ints1000
BenchmarkChunk/ints1000-12                312517          3871 ns/op
Benchmark without using copy:

BenchmarkChunk
BenchmarkChunk/strings_10
BenchmarkChunk/strings_10-12            52708929            22.42 ns/op
BenchmarkChunk/strings_100
BenchmarkChunk/strings_100-12           12681414            93.45 ns/op
BenchmarkChunk/strings_1000
BenchmarkChunk/strings_1000-12           2022960           599.6 ns/op
BenchmarkChunk/ints10
BenchmarkChunk/ints10-12                52086441            22.50 ns/op
BenchmarkChunk/ints100
BenchmarkChunk/ints100-12               12925526            90.06 ns/op
BenchmarkChunk/ints1000
BenchmarkChunk/ints1000-12               1978053           591.1 ns/op

[dsolerh]

I think in this case the use of copy can be delegated to the user of the library, since the most straightforward way to make the implementation safe is to copy the collection values like:

func Chunk[T any, Slice ~[]T](collection Slice, size int) []Slice {
    if size <= 0 {
        panic("Second parameter must be greater than 0")
    }

    chunksNum := len(collection) / size
    if len(collection)%size != 0 {
        chunksNum += 1
    }

    collectionCopy := make(Slice, len(collection))
    copy(collectionCopy, collection)
    result := make([]Slice, 0, chunksNum)

    for i := 0; i < chunksNum; i++ {
        last := (i + 1) * size
        if last > len(collectionCopy) {
            last = len(collectionCopy)
        }
        result = append(result, collectionCopy[i*size:last:last])
    }

    return result
}

the one thing I think should be improved is the documentation for the function to reflect this behaviour. Also cause the only scenario for the shared memory to become a problem is if the user makes a change in either the original array or the chunks like original[i]=<some value> or chunks[i][j]=<some value>.

[dagenius007]

This is a case of efficiency versus safety, and we need to choose the better option. I would prefer to prioritize safety to avoid potential issues with modifying the collections slice.

[dsolerh]

My point is precisely that there's no 'vs', both options are possible, the documentation just need to reflect the potential issues, cause there may be many cases in which there's no need for the safety. You can have a Chunk and a ChunkSafe (maybe not with these names) and the user can choose which one is better suited for his need.

[dagenius007]

I totally agree creating a ChunkSafe function and the user chooses based on what he want to use them for.

[dagenius007]

@samber what do you think about this? I can create a PR with regards to these suggestions.

[shoham-b]

Could you please share the code for the original benchmark? I think maybe it copies each slice individually. Copying as @dsolerh suggested is way faster as it saves the copy calls and enables using SIMD and unroll.

In general, copy shouldn't take that long, it has a tone of optimizations. On my computer I get this results -

cpu: Apple M1 Pro
Benchmark_Chunk_int
Benchmark_Chunk_int/Chunk_100
Benchmark_Chunk_int/Chunk_100-8                     17508577            58.67 ns/op
Benchmark_Chunk_int/ChunkSafeTheRightWay_100
Benchmark_Chunk_int/ChunkSafeTheRightWay_100-8          13027635            96.56 ns/op
Benchmark_Chunk_int/ChunkSafeTheSlowWay_100
Benchmark_Chunk_int/ChunkSafeTheSlowWay_100-8            5968666           192.8 ns/op
Benchmark_Chunk_int/Chunk_1000
Benchmark_Chunk_int/Chunk_1000-8                         3095260           376.4 ns/op
Benchmark_Chunk_int/ChunkSafeTheRightWay_1000
Benchmark_Chunk_int/ChunkSafeTheRightWay_1000-8          2336620           464.6 ns/op
Benchmark_Chunk_int/ChunkSafeTheSlowWay_1000
Benchmark_Chunk_int/ChunkSafeTheSlowWay_1000-8            709839          1658 ns/op
Benchmark_Chunk_int/Chunk_10000
Benchmark_Chunk_int/Chunk_10000-8                         395826          2939 ns/op
Benchmark_Chunk_int/ChunkSafeTheRightWay_10000
Benchmark_Chunk_int/ChunkSafeTheRightWay_10000-8          309154          3974 ns/op
Benchmark_Chunk_int/ChunkSafeTheSlowWay_10000
Benchmark_Chunk_int/ChunkSafeTheSlowWay_10000-8            76291         15568 ns/op
PASS

This can vary dramatically between architectures, and sizes of slice, but in general a copy is something that happens, e.g. when appending to an array such that it requires more space.

This can have even more awkward leak when appending to the chunked slice before setting at index

    s := make([]int, 1000)
    chunks := lo.Chunk(s, 10)
    firstChunk := chunks[0]
    firstChunk = append(firstChunk, 666) // might or might not realloc the chunk, decided internally.
    firstChunk[0] = 666                  // might or might not also modify "s"

I think the default behavior should be safe, and if someone wants a cutting edge optimizations then they should implement it themselves and take full responsibility.

So given all of that, I vote for putting the safe as the default Chunk function.