Memory-friendly 2d array with variable-length rows

arr.rs

pub const ARR: &[&[i32]] = &[
&[0],
&[0,1],
&[0,1,2],
&[0,1,2,3],
//&[...........],
&[0,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,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498],
&[0,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,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499],
];

cargo_bench_out.log

   Compiling variable_row_array v0.1.0 (/***/variable_row_array)
    Finished bench [optimized] target(s) in 1.74s
     Running unittests src/lib.rs (target/release/deps/variable_row_array-51b4db3f3fd0ef61)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/release/deps/variable_row_array-a139c351cd24ee7b)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running benches/arr.rs (target/release/deps/arr-61efe39025139293)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running benches/variable_row_array_bench.rs (target/release/deps/variable_row_array_bench-454190100c1ae385)
Gnuplot not found, using plotters backend
VariableRowArray.get    time:   [1.9030 ns 1.9101 ns 1.9210 ns]
Found 7 outliers among 100 measurements (7.00%)
  7 (7.00%) high severe

ArrayOfSlices index     time:   [1.9304 ns 1.9334 ns 1.9369 ns]
Found 9 outliers among 100 measurements (9.00%)
  3 (3.00%) high mild
  6 (6.00%) high severe

variable_row_array_bench.rs

// https://users.rust-lang.org/t/memory-friendly-2d-array-with-variable-length-rows/99330
mod arr;
use arr::ARR;
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use variable_row_array::VariableRowArray;

pub fn variable_row_array_benchmark(c: &mut Criterion) {
    const VRA: VariableRowArray<i32, 125250, 501> = VariableRowArray::new_with_data(&ARR);

    c.bench_function("VariableRowArray.get", |b| {
        b.iter(|| {
            black_box(VRA.get(10, 0));
            black_box(VRA.get(10, 5));
            black_box(VRA.get(10, 9));

            black_box(VRA.get(255, 0));
            black_box(VRA.get(255, 112));
            black_box(VRA.get(255, 254));

            black_box(VRA.get(499, 0));
            black_box(VRA.get(499, 255));
            black_box(VRA.get(499, 499));
        });
    });
}

pub fn array_of_slices_benchmark(c: &mut Criterion) {
    c.bench_function("ArrayOfSlices index", |b| {
        b.iter(|| {
            black_box(ARR[10][0]);
            black_box(ARR[10][5]);
            black_box(ARR[10][9]);

            black_box(ARR[255][0]);
            black_box(ARR[255][112]);
            black_box(ARR[255][224]);

            black_box(ARR[499][0]);
            black_box(ARR[499][225]);
            black_box(ARR[499][499]);
        });
    });
}

criterion_group!(
    benches,
    variable_row_array_benchmark,
    array_of_slices_benchmark
);
criterion_main!(benches);