LE query micro benchmark

C# test via PInvoke

        [Test]
        public void CursorShouldGetLessOrEqual() {
            
            _db = _txn.OpenDatabase(flags: DbFlags.None);
            var db2 = _txn.OpenDatabase("test_le",
                DbFlags.Create | DbFlags.IntegerKey);

            using (var cur = _txn.CreateCursor(db2)) {

                int[] keys = new int[10000000];
                for (int i = 0; i < 10000000; i++) {
                    keys[i] = i * 2;
                }

                unsafe
                {
                    foreach (var k in keys) {
                        var buffer = BitConverter.GetBytes(k);
                        fixed (byte* dataPtr = &buffer[0])
                        {
                            ValueStructure mdb_val = new ValueStructure(new IntPtr(4), (IntPtr)dataPtr);
                            cur.PutPointers(mdb_val, mdb_val, CursorPutOptions.None);
                        }
                    }

                    // all GE and LE must be present one step away from each lookup keys
                    int[] lookupKeys = new int[9999];
                    for (int i = 0; i < 9999; i++) {
                        lookupKeys[i] = i * 2 * 10 + 1;
                    }

                    var sw = new Stopwatch();
                    sw.Start();
                    for (int i = 0; i < 100; i++) {
                        foreach (var lookupKey in lookupKeys) {
                            var buffer = BitConverter.GetBytes(lookupKey);
                            fixed (byte* dataPtr = &buffer[0])
                            {
                                ValueStructure mdb_val = new ValueStructure(new IntPtr(4), (IntPtr)dataPtr);
                                var resultKVP = cur.GetPointers(CursorOperation.SetRange, mdb_val, mdb_val);
                                int returnedKey = *(int*)resultKVP.Value.Key.Data;
                                if (returnedKey != lookupKey + 1)
                                    throw new Exception("Wrong GE lookup");
                            }
                        }
                    }
                    sw.Stop();
                    Console.WriteLine("GE elapsed: " + sw.ElapsedMilliseconds);

                    sw.Restart();
                    for (int i = 0; i < 100; i++) {
                        foreach (var lookupKey in lookupKeys) {
                            var buffer = BitConverter.GetBytes(lookupKey);
                            fixed (byte* dataPtr = &buffer[0]) {
                                ValueStructure mdb_val = new ValueStructure(new IntPtr(4), (IntPtr) dataPtr);
                                var resultKVP = cur.GetPointersLE(mdb_val, mdb_val);
                                int returnedKey = *(int*) resultKVP.Value.Key.Data;
                                //Console.WriteLine(lookupKey + " -> " + returnedKey);
                                if (returnedKey != lookupKey - 1)
                                    throw new Exception("Wrong LE lookup: " + returnedKey.ToString());
                            }
                        }
                    }
                    sw.Stop();
                    Console.WriteLine("LE elapsed: " + sw.ElapsedMilliseconds);


                    foreach (var k in keys) {
                        var buffer = BitConverter.GetBytes(k);
                        fixed (byte* dataPtr = &buffer[0])
                        {
                            ValueStructure mdb_val = new ValueStructure(new IntPtr(4), (IntPtr)dataPtr);
                            cur.PutPointers(mdb_val, mdb_val, CursorPutOptions.None);
                        }
                    }


                    sw.Restart();
                    for (int i = 0; i < 100; i++) {
                        for (int j = lookupKeys.Length-1; j >=0 ; j--) {
                            var buffer = BitConverter.GetBytes(lookupKeys[j]);
                            fixed (byte* dataPtr = &buffer[0])
                            {
                                ValueStructure mdb_val = new ValueStructure(new IntPtr(4), (IntPtr)dataPtr);
                                var resultKVP = cur.GetPointersLE(mdb_val, mdb_val);
                                int returnedKey = *(int*)resultKVP.Value.Key.Data;
                                //Console.WriteLine(lookupKey + " -> " + returnedKey);
                                if (returnedKey != lookupKeys[j] - 1)
                                    throw new Exception("Wrong LE lookup: " + returnedKey.ToString());
                            }
                        }
                    }
                    sw.Stop();
                    Console.WriteLine("LE elapsed 2: " + sw.ElapsedMilliseconds);

                    // Reverse order
                    sw.Restart();
                    for (int i = 0; i < 100; i++) {
                        for (int j = lookupKeys.Length - 1; j >= 0; j--) {
                            var buffer = BitConverter.GetBytes(lookupKeys[j]);
                            fixed (byte* dataPtr = &buffer[0])
                            {
                                ValueStructure mdb_val = new ValueStructure(new IntPtr(4), (IntPtr)dataPtr);
                                var resultKVP = cur.GetPointers(CursorOperation.SetRange, mdb_val, mdb_val);
                                int returnedKey = *(int*)resultKVP.Value.Key.Data;
                                if (returnedKey != lookupKeys[j] + 1)
                                    throw new Exception("Wrong GE lookup");
                            }
                        }
                    }
                    sw.Stop();
                    Console.WriteLine("GE elapsed 2: " + sw.ElapsedMilliseconds);


                    

                }
            }
        }

mdb_cursor_get_le

int mdb_cursor_get_le(MDB_cursor *mc, MDB_val *key, MDB_val *data)
{   
    // need to store initial value before set_range, which overwrites *key
    MDB_val* original = malloc(sizeof(MDB_val));
    original->mv_size = key->mv_size;
    original->mv_data = malloc(original->mv_size);
    memcpy(original->mv_data, key->mv_data, key->mv_size);
    MDB_txn *txn = mdb_cursor_txn(mc);
    MDB_dbi dbi = mdb_cursor_dbi(mc);
    int rc;
    rc = mdb_cursor_get(mc, key, data, MDB_SET_RANGE);
    if(mdb_cmp(txn, dbi, original, key) < 0){
        free(original->mv_data);
        free(original);
        return mdb_cursor_get(mc, key, data, MDB_PREV);
    };
    free(original->mv_data);
    free(original);
    return rc; // equal
}

Should just use:

   MDB_val orig = *key;
   ...
   if (mdb_cmp(txn, dbi, &orig, key) < 0)
       return mdb_cursor_get(mc, key, data, MDB_PREV);

no need to alloc or copy anything.

Thank you! Now GE and LE are equal in speed. Need to re-read K&R chapter on pointers.