Implementing Bloom Filter in Dart

This post is the output of this book.

Advanced Algorithms and Data Structures

I tried to implement Bloom Filter in Dart this time. You can clone my repository and run the code in devcontainer. Check my GitHub repository.

What is Bloom Filter used for

Let’s consider the case of the spell checker. The system needs to have tons of words in a database. Then, the system checks one word by one word in your document.

However, the more entries are registered in the database, the slower the response becomes. Furthermore, it requires more memory if all the words need to be loaded.

We don’t have to make sure if the target word exists in the database. We just want to know if the target word doesn’t exist in it.

Bloom Filter comes in here. Instead of having words, it uses bit array to have the data. So, it can reduce a lot of memory comparing storing the data itself. For example, a data goes through 3 hash functions in the following image for inserting data.

It uses only 3 bits for data but some of the bits could be used for other data. So, you can imagine that a lot of memory can be saved.

When you want to search for target data in it, the same hash functions need to be applied to the data. If all the elements on the indexes are 1, it means that the data exists in the database. If one of them is 0, the data doesn’t exist.

However, as already mentioned, all the elements could be 1 even though the data is NOT registered. This is called False Positive. To avoid False Positive, the bit array size needs to be big enough.

False Positive can happen in Bloom Filter but False Negative doesn’t happen. False Negative means in this case that the function says that the data doesn’t exist even though it’s actually registered.

Implementation

This is the complete code of the Bloom Filter in Dart language.

import 'dart:ffi';
import 'dart:math';
import 'dart:typed_data';

import 'package:fnv/fnv.dart';
import 'package:murmurhash/murmurhash.dart';

class BitCoordinates {
  final int elementIndex;
  final int bitIndex;
  BitCoordinates({
    required this.elementIndex,
    required this.bitIndex,
  });
}

typedef HashFunction = int Function(int h1, int h2);

class BloomFilter {
  int size = 0;
  final int maxSize;
  late final int seed;
  late final int numberOfBits;
  late final List<HashFunction> hashFunctions;
  late final Int8List bitsArray;
  late final int numberOfHashFunctions;
  final bitsPerElement = 8;

  BloomFilter({
    required this.maxSize,
    maxTolerance = 0.01,
    Uint64? seed,
  }) {
    if (seed == null) {
      this.seed = Random().nextInt(pow(2, 32).toInt());
    }

    if (maxSize <= 0) {
      throw Exception(
          "maxSize must be positive number. Actual value: [$maxSize] ");
    }

    if (maxTolerance > 1 || maxTolerance < 0) {
      throw Exception(
          "maxTolerance must be 0 < x < 1. . Actual value: [$maxTolerance]");
    }

    numberOfBits = -(maxSize * log(maxTolerance) / ln2 / ln2).ceil();
    numberOfHashFunctions = -(log(maxTolerance) / ln2).ceil();
    final numberOfElements = (numberOfBits / bitsPerElement).ceil();
    bitsArray = Int8List(numberOfElements);
    hashFunctions = _initiHashFunctions(numberOfHashFunctions);
  }

  BitCoordinates findBitCoordinates(int index) {
    final bitsPerElement = 8 * bitsArray.elementSizeInBytes;
    final elementIndex = (index / bitsPerElement).floor();
    final bitIndex = index % bitsPerElement;
    return BitCoordinates(elementIndex: elementIndex, bitIndex: bitIndex);
  }

  int readBit(int index) {
    final coordinates = findBitCoordinates(index);
    final targetBit =
        bitsArray[coordinates.elementIndex] & (1 << coordinates.bitIndex);
    // return 0 or 1
    return targetBit >> coordinates.bitIndex;
  }

  Int8List writeBit(int index) {
    final coordinates = findBitCoordinates(index);
    bitsArray[coordinates.elementIndex] =
        bitsArray[coordinates.elementIndex] | (1 << coordinates.bitIndex);
    return bitsArray;
  }

  bool contains(String key, {List<int>? positions}) {
    positions ??= _key2Positions(seed, key);
    return positions.every((element) => readBit(element) != 0);
  }

  void insert(String key) {
    final positions = _key2Positions(seed, key);
    if (contains(key, positions: positions)) {
      return;
    }

    size++;
    for (var element in positions) {
      writeBit(element);
    }
  }

  num falsePositiveProbability() {
    final a = pow(e, -numberOfHashFunctions * size / numberOfBits);
    return pow((1 - a), numberOfHashFunctions);
  }

  List<int> _key2Positions(int seed, String key) {
    final hashM = MurmurHash.v3(key, seed);
    final hashF = fnv1_32_s(key);
    return hashFunctions.map((h) => h(hashM, hashF)).toList();
  }

  List<HashFunction> _initiHashFunctions(int numberOfHashFunctions) {
    return List.generate(
      numberOfHashFunctions,
      (int index) => ((int h1, int h2) =>
          (h1 + index * h2 + index * index) % numberOfBits),
    );
  }
}

Constructor

maxSize is max size of the Bloom Filter.
If maxTolerance is big, it often causes false positive.

BloomFilter({
  required this.maxSize,
  maxTolerance = 0.01,
  Uint64? seed,
}) {
  if (seed == null) {
    this.seed = Random().nextInt(pow(2, 32).toInt());
  }
  if (maxSize <= 0) {
    throw Exception(
        "maxSize must be positive number. Actual value: [$maxSize] ");
  }
  if (maxTolerance > 1 || maxTolerance < 0) {
    throw Exception(
        "maxTolerance must be 0 < x < 1. . Actual value: [$maxTolerance]");
  }
  numberOfBits = -(maxSize * log(maxTolerance) / ln2 / ln2).ceil();
  final numberOfHashFunctions = -(log(maxTolerance) / ln2).ceil();
  final numberOfElements =
      (numberOfBits / bitsPerElement).ceil();
  bitsArray = Int8List(numberOfElements);
  hashFunctions = _initiHashFunctions(numberOfHashFunctions);
}

I actually don’t understand the formula of the lines where log notation is used. But it’s not necessary to dive into the details.

_initiHashFunctions

This generates hash functions. It has two => in the function. This is called Carried Function or Carrying Function.

typedef HashFunction = int Function(int h1, int h2);

List<HashFunction> _initiHashFunctions(int numberOfHashFunctions) {
  return List.generate(
    numberOfHashFunctions,
    (int index) => ((int h1, int h2) =>
        (h1 + index * h2 + index * index) % numberOfBits),
  );
}

It returns functions that require two parameters. All the functions have a different value of index.

Check the following post if you want to know the currying function in more detail.

JavaScript/TypeScript currying arrow function

The currying or curried function is an arrow function that returns an arrow function. If the internal object also return...

54.147.5.15

findBitCoordinates

BitCoordinates findBitCoordinates(int index) {
  final bitsPerElement = 8 * bitsArray.elementSizeInBytes;
  final elementIndex = (index / bitsPerElement).floor();
  final bitIndex = index % bitsPerElement;
  return BitCoordinates(elementIndex: elementIndex, bitIndex: bitIndex);
}

In dart, Int8List is provided, so one element consists of 8 bits. If you implement it in other languages that don’t offer 1-byte data type, it needs to be adjusted with this

final bitsPerElement = 8 * bitsArray.elementSizeInBytes;

Then, this statement gets the index of the target element. If the index is 17 and bitsPerElement is 8, the result is 2.

final elementIndex = (index / bitsPerElement).floor();

The index in the target element can be calculated with mod.

final bitIndex = index % bitsPerElement;

readBit

int readBit(int index) {
  final coordinates = findBitCoordinates(index);
  final targetBit =
      bitsArray[coordinates.elementIndex] & (1 << coordinates.bitIndex);
  // return 0 or 1
  return targetBit >> coordinates.bitIndex;
}

The target bit becomes 1 if it is already 1. Otherwise, 0. 1 << 3 for example, means that 1 is moved to the left side. 0001 becomes 1000. All the other bits become 0 in this statement.

final targetBit =
      bitsArray[coordinates.elementIndex] & (1 << coordinates.bitIndex);

Then it moves the bit right side. This returns 0 or 1.

return targetBit >> coordinates.bitIndex;

writeBit

Int8List writeBit(int index) {
  final coordinates = findBitCoordinates(index);
  bitsArray[coordinates.elementIndex] =
      bitsArray[coordinates.elementIndex] | (1 << coordinates.bitIndex);
  return bitsArray;
}

This is basically the same as readBit.

contains

List<int> _key2Positions(int seed, String key) {
  final hashM = MurmurHash.v3(key, seed);
  final hashF = fnv1_32_s(key);
  return hashFunctions.map((h) => h(hashM, hashF)).toList();
}

bool contains(String key, {List<int>? positions}) {
  positions ??= _key2Positions(seed, key);
  return positions.every((element) => readBit(element) != 0);
}

We use two different hash functions. hashM and hashF are used in the following function which was generated in _initiHashFunctions.

((int h1, int h2) => (h1 + index * h2 + index * index) % numberOfBits)

positions needs to be calculated only when it’s null. This is done to avoid the same calculation twice when inserting data.

positions ??= _key2Positions(seed, key);

// equivalent to the following
if (positions == null) {
  positions = _key2Positions(seed, key);
}

The data exists if all the bits are 1.

return positions.every((element) => readBit(element) != 0);

insert

void insert(String key) {
  final positions = _key2Positions(seed, key);
  if (contains(key, positions: positions)) {
    return;
  }

  size++;
  for (var element in positions) {
    writeBit(element);
  }
}

If the data is already added, it’s not necessary to add it again. So the positions need to be calculated first. If it doesn’t exist, increment the size, which is the number of registered elements. This is used to estimate the filter’s false positive ratio.

Try to use Bloom Filter to check if a number doesn’t exist

Let’s use the Bloom Filter. I mentioned about spell checker but it’s cumbersome to register lots of correct words. Let’s use numbers instead in this example.

The following class emulates slow storage. It takes more than 100 milliseconds if you need to check whether the target number exists in the storage.

class SlowStorage {
  final Set<int> _numbers =
      List.generate(1000, (index) => Random().nextInt(numberRange)).toSet();

  Iterable<int> get numbers => _numbers.toList();
  int get length => _numbers.length;

  bool contains(int num) {
    sleep(Duration(milliseconds: 100));
    return _numbers.contains(num);
  }
}

We don’t want to use this class directly to avoid the performance issue. So, let’s wrap the class with Bloom Filter.

class NumChecker {
  late final BloomFilter _bloomFilter;
  final _slowStorage = SlowStorage();

  NumChecker() {
    final size = 2 * _slowStorage.length;
    _bloomFilter = BloomFilter(maxSize: size, maxTolerance: 0.01);
    print(_slowStorage.numbers.join(","));

    // Register all the numbers into Bloom Filter
    for (final num in _slowStorage.numbers) {
      _bloomFilter.insert(num.toString());
    }
  }

  bool contains(int num) {
    if (_bloomFilter.contains(num.toString())) {
      final actual = _slowStorage.contains(num);
      if (!actual) {
        print("FALSE POSITIVE!!! Value: $num");
      }
      return actual;
    }
    return false;
  }
  void printFalsePositiveRatio(){
    print("False Positive Ratio: ${_bloomFilter.falsePositiveProbability()}");
  }
}

If Bloom Filter contains function returns true, it could be False Positive. Therefore, it needs to access the actual storage.

Then, let’s use it.

void main(List<String> args) {
  final reader = NumChecker();

  for (int i = 0; i <= 50; i++) {
    final val = Random().nextInt(numberRange);
    final watch = Stopwatch()..start();
    reader.contains(val);
    watch.stop();
    print("$val: \t${watch.elapsedMicroseconds} μs");
  }
  reader.printFalsePositiveRatio();
}

The result is the following.

$ dart main.dart 
4463,3165,9591,9122,393,5585,7650,9345,4000,6046,2947,3645,8766,7399,6183,2068,2352,9779,6405,1322,5691,1100,8786,3954,382,4921,7911,3641,6193,7343,3880,2960,4076,157,5834,3800,6932,1410,4016,5386,1383,5555,3615,319,5628,5895,6328,4852,272,2372,1126,3074,3327,6210,5532,2617,5922,5720,4183,6773,8301,3026,2366,6562,5647,1587,7151,4098,1819,1401,4293,5543,7753,3665,3734,1503,6311,4046,6961,1414,9369,1617,4205,8251,3643,310,6265,9383,2084,688,9694,2661,5709,9043,7094,8288,8869,4603,8611,3116,7254,2857,2781,6194,4692,517,8549,3431,8319,2672,5353,6901,5385,6452,3606,2431,464,4863,7505,8833,3083,751,403,2514,258,6242,702,3968,7214,2483,8782,9066,2155,4429,823,9704,2033,7180,743,8971,3449,8345,4224,635,1748,9362,3229,2878,7161,1214,4662,539,5645,7728,6195,3100,7582,5487,5381,2385,2925,9280,9743,6568,8310,5398,6565,106,1334,7683,2874,9934,9137,1180,7653,4159,3756,9457,1931,630,4343,505,3245,436,3436,4593,5480,2889,6013,7876,8645,2515,5925,7816,850,9095,7610,6943,4976,9799,7392,4083,5874,1110,6384,4577,6549,1586,7206,5745,4349,9770,8612,2723,3304,7948,562,7047,2459,1974,4329,7727,2067,3740,8524,3941,6053,4580,7565,9828,1509,8386,1890,9353,6696,4222,9145,9301,5078,3161,3085,2807,994,9502,4816,3517,5188,4897,5785,5719,790,4014,5227,4669,1373,1387,7571,3249,3998,1272,3633,3912,5675,7574,9172,5387,7908,7824,9376,670,4775,9611,8550,98,4037,6257,260,4185,4878,6536,5497,553,7327,2787,3836,9463,1086,3784,3701,2445,8283,5335,2695,4988,9764,5077,7119,2682,786,5711,4968,5863,4591,5473,9734,9695,2392,6630,9297,7328,5197,1570,867,1686,2678,4377,5594,3311,6761,3935,8653,1038,2052,1090,3692,4166,6814,3123,7606,1708,8847,2601,7696,7441,2040,7429,348,1348,4438,845,1245,6614,3741,8894,8731,1113,9204,7959,3241,4381,9708,4572,8603,1573,6294,2172,1649,7715,6868,3252,7998,847,8234,6354,7568,7127,6770,4699,830,3683,6102,5176,9495,29,2416,9667,3250,4065,4243,9863,5761,7456,8648,119,1896,4810,4274,8927,1999,6531,4459,7525,5199,3609,2278,9909,6502,6121,1511,7810,5472,1645,2513,5704,372,1840,7729,5772,2648,6486,9077,5915,7358,8968,3407,8715,5347,4273,1923,2640,6491,9428,4923,7287,9621,967,1801,6681,1728,4740,5582,3946,6138,5195,9148,5400,4995,692,9533,9412,3827,7549,5723,5215,9392,2472,549,4622,5100,7967,5887,1659,9664,291,8102,1098,3764,9648,9813,6555,9343,5213,1985,9777,7348,7512,5132,6098,5344,6706,5844,2485,4216,8516,6394,8906,2818,5181,5975,5536,6504,4566,4974,3274,579,6844,1620,6455,9957,4871,7575,4048,9588,37,6103,4468,5354,3864,9040,6782,4393,7681,2453,7760,9608,5465,6132,9228,2543,7170,3697,1949,9688,1037,9325,1508,9229,7415,7752,7820,7621,4118,2618,5706,9444,2014,504,6279,2610,5577,1358,2019,9064,1715,4176,7242,3102,429,1174,7716,2846,3234,2144,2653,8596,4173,1046,3684,828,4361,6302,3341,7781,8502,1664,9224,5744,3050,9950,8962,6111,2350,1222,6580,7373,2750,5147,8413,5066,3148,9006,2051,9983,6117,2335,1996,7014,2249,1872,6743,515,3753,1791,1559,5624,3208,9221,3979,6259,9231,627,7799,1190,9503,4602,1628,6009,174,9180,1930,4888,9390,8154,1879,981,459,5070,1283,1924,140,51,9212,2553,1626,3039,9012,2581,156,929,3698,2733,9171,7302,6068,871,5763,8716,7709,6858,4951,6253,7891,7943,9893,7306,4928,2635,6399,8937,7801,5161,6712,6926,7800,1562,9718,6206,6392,1302,1420,1786,2612,2088,2611,2752,2720,8243,7418,1149,5308,659,8377,2984,1346,906,4643,3913,7779,7387,7016,3566,3559,5832,1543,2481,3031,9806,2233,9336,1467,5052,7979,1527,8488,8726,9581,3484,4983,3065,2699,9929,7792,9655,6751,7557,5166,2097,5030,5518,9516,5339,3302,7926,5637,9403,8378,7952,2833,8926,3207,7300,4764,6321,5105,9375,9441,3766,7676,2922,2099,9504,236,585,7017,963,1849,5619,4250,2125,8064,7612,4287,9513,1916,2002,6074,1498,1004,6890,5570,2194,1862,1031,3112,5521,3284,3351,3513,2190,7304,8309,334,6410,2537,2652,2912,8734,1673,6032,5560,3523,7588,2879,95,2116,5986,8121,5421,5155,4284,471,9341,729,176,9805,4857,5992,8597,3852,2815,342,5546,4746,5528,5814,8106,7963,610,9575,2423,9461,9844,5857,1741,2890,9350,2117,4072,3531,8690,8706,8925,853,9965,4524,8529,4655,2927,6201,1798,779,9626,1330,8918,5981,7468,3727,6482,74,6048,8358,6108,6951,5349,374,2959,7260,57,3220,2860,6501,3762,115,725,2777,5608,8307,3,4936,723,2531,1354,3308,1225,8042,9255,9354,5044,3922,7270,6135,7075,1729,8334,5784,5776,7491,5284,9692,1279,9177,4082,7883,6497,9442,3460,3743,9562,7770,6972,2849,200,363,4378,1335,6510,5636,4698,2734,2419,7815,6176,1560,4613,9956,4221,9206,6168,6472,2676,5071,2054,9839,1856,5293,7344,3712,13,448,6750,3702,7146,1777,4865,2074,1155,9130,6450,9044,2332,5541,5525,6211,8776,67,1793,8934,4723,2102,3809,16,5377,600,502,9047,2701,5933,8976,9479,5043,1782,479,7203,3238,7543,8329,5410,6037,3818,2582,6356,3152,7376,9030
9449:   900 μs
8130:   74 μs
6079:   578 μs
5006:   31 μs
7897:   15 μs
4604:   9 μs
9409:   11 μs
7493:   22 μs
8482:   17 μs
6368:   11 μs
4838:   12 μs
9080:   12 μs
1412:   17 μs
6794:   11 μs
7690:   67 μs
3076:   13 μs
5479:   21 μs
4737:   12 μs
3011:   12 μs
3847:   10 μs
3333:   17 μs
7416:   16 μs
9932:   12 μs
8801:   17 μs
3635:   15 μs
3295:   22 μs
1103:   13 μs
3453:   14 μs
1507:   15 μs
4993:   13 μs
7307:   27 μs
6427:   12 μs
3332:   13 μs
7353:   12 μs
7061:   19 μs
6394:   101966 μs
747:    38 μs
4642:   13 μs
9557:   24 μs
4278:   24 μs
6961:   100183 μs
3001:   118 μs
3448:   71 μs
7690:   54 μs
4721:   71 μs
7723:   82 μs
3621:   48 μs
7206:   100296 μs
1638:   189 μs
1970:   68 μs
444:    49 μs
False Positive Ratio: 0.00037676701857460916

As you can see from the result, the response time is quite short if it doesn’t exist in the storage. If the number exists in the database, it takes a much longer time because it needs to access the slow storage.

Since maxTolerance is 1%, False Positive didn’t occur in this test. Let’s change the value to 0.3.

$ dart main.dart 
5487,5607,6923,9521,2623,7397,5162,400,6920,3287,7006,4920,7485,9659,2073,7658,3537,3034,3148,7483,5985,5030,3428,4741,529,1406,1036,3425,5695,1998,9537,187,9553,3143,600,4733,9000,1117,843,6612,7476,1327,2782,4572,3347,32,2538,5578,5015,6987,5742,1641,5136,5887,9718,5058,9595,7482,5843,4465,9418,5634,4523,5625,6671,2442,4226,249,9313,9967,5512,281,8664,4747,8918,7822,4545,1869,2907,8206,1988,748,8114,428,2324,9207,2624,2385,3589,8362,9267,6073,5840,1270,3263,2973,4923,4640,1932,5139,6652,9558,273,3782,1135,3493,2859,6884,9175,6909,8755,5867,7706,3780,5255,5027,7251,2943,8500,7584,2389,6372,9434,3632,1802,5066,573,6481,9749,3659,7569,7400,8944,6320,6199,4719,4905,2128,1496,8441,1499,7322,3631,2979,2318,1691,5917,6919,235,55,1475,7115,4774,1458,8654,9422,2480,9883,5188,4618,7968,5833,7506,9316,8059,537,6766,2931,6135,8496,8023,288,6218,9012,2516,9168,8383,1330,1125,2941,4718,4067,3832,8949,6260,6781,3570,9,7793,5838,5018,8603,7909,5376,9873,576,5923,5168,3993,7098,5158,9141,3572,7106,2995,3706,5200,430,6602,13,3947,9650,7186,494,1313,2537,1821,2577,6376,7861,9382,4099,9743,8663,554,3284,306,4794,7117,2869,7086,8411,6597,8035,9751,7114,2468,5309,6973,7558,2272,4851,4650,6733,2211,7110,3557,7544,1246,9554,1866,8990,1237,4217,3019,1286,1509,9411,337,5164,4043,7036,8572,9391,8525,8226,3000,8596,7823,5665,6604,3579,4346,460,7457,3304,3133,3309,9916,760,7703,3558,1456,819,4567,2909,7300,7559,9742,1056,761,4980,8182,4590,1930,8764,8517,9031,758,9380,1266,8848,5106,5284,5165,525,5185,1931,6329,3815,7958,4277,4392,9498,7859,9375,7940,6924,1708,312,9920,4925,8291,857,9981,6618,3190,5425,1528,3984,7461,9777,9465,7507,1919,1128,7817,7549,5023,648,4745,3,6544,5332,1654,5567,8561,5052,1697,5276,6523,6173,4810,4377,7362,8006,7979,4978,6484,7796,5242,6805,9243,7008,5860,9475,520,4401,4020,9171,7273,2135,7500,403,8420,2377,3644,8086,1114,533,8935,2252,5123,9519,7502,9885,4855,2672,8719,1873,7519,7188,1049,771,8650,9314,2338,1728,4984,9353,9273,981,4171,4836,2048,6408,937,644,2337,42,8953,6863,6090,2920,6179,4249,2653,1618,3373,7405,4225,5256,8716,4442,9190,7150,3144,8189,4759,8152,5961,2041,7269,5318,5077,2056,3337,6810,7767,8443,4005,4829,5323,176,3859,2335,6026,7410,5349,4220,4967,9265,3917,2235,2552,2514,7432,4188,3587,575,5070,1304,7791,2432,3087,776,5414,4531,4355,3762,2434,1720,8682,7957,8945,9840,5585,7130,7949,5934,6236,8334,8143,2257,1693,1031,1795,452,7447,6811,3115,4136,2222,9354,7099,8942,9232,7123,1187,4353,4371,9865,1991,4518,8073,2408,9691,4591,2708,616,4613,8166,8394,1514,2536,466,1922,6124,3038,8305,2430,1021,650,2873,1485,7719,5962,6611,8919,8170,2270,1589,9526,1653,4236,2416,8313,3976,2402,127,1603,4434,2130,9288,3553,500,1420,3603,1511,84,9935,1645,2843,9067,7991,3861,888,2848,6476,5842,6482,8311,3708,5227,8041,9778,717,5294,8747,892,4841,7438,2321,8757,7572,6111,5495,3897,1176,8148,4361,6843,7620,9527,2415,4875,7713,6689,2649,7756,8997,7871,1962,7513,6201,5384,5960,7902,6824,2526,593,8234,5942,7230,8195,9715,4379,9310,6030,868,919,9683,659,18,3737,1680,961,767,4824,2769,6890,3969,995,1582,998,1402,3030,1092,5311,4348,6840,5781,2173,3039,6867,2250,9826,3452,8514,107,259,4514,5693,9205,6834,2613,9242,768,3622,2830,2479,2383,7702,8934,8669,2846,2037,2581,9922,4687,1138,9371,9639,3485,9583,9512,7867,1796,7669,9548,1256,2551,3703,1517,8414,3961,863,5697,2046,8928,7892,4292,7831,742,8759,5768,3008,8504,166,7278,9632,8536,5798,6048,3310,6296,1081,2674,2650,4727,2662,2307,7381,1656,1400,8957,3845,2498,1563,2628,1948,1835,9857,972,5182,21,4409,1439,8022,640,6219,3255,1923,7659,702,3614,8678,6463,8008,4094,196,1913,1030,9790,8346,6121,8556,1731,4127,8653,9379,9496,1144,7212,9333,2059,2197,1591,5014,8400,2737,2486,8519,8679,9430,2493,8131,2139,9974,491,5498,9516,8468,1915,6189,6272,2336,3956,5264,6825,3443,1701,4207,7199,2085,1419,7589,170,8178,4481,2101,8827,7792,4281,6250,2625,6859,9584,3800,7717,7770,410,9331,5417,3928,4872,8457,2802,1668,2116,4970,4706,8740,2477,6325,3639,7573,7577,8365,9989,8194,4728,6732,7610,1806,8109,8501,8216,9813,60,6798,5138,3883,1121,7439,8783,2828,3601,6727,8418,3911,9941,6901,5272,4493,5277,3124,9578,3502,8707,6595,7012,9206,9081,8167,9576,1524,1649,9106,7379,3851,7219,2153,8264,982,1689,6579,2373,5872,3330,5576,4284,5730,834,2792,9202,3769,122,4949,8451,4202,397,7849,3381,5201,5967,912,9701,1232,8780,3953,7163,3159,6049,5599,5239,9775,4694,8715,8635,429,6033,3647,3408,2340,229,5467,4496,2220,7983,6687,7349,366,7868,8393,1632,6340,9356,6471,2142,9555,4322,4864,5551,7730,7422,8448,2362,4847,6626,915,1113,1955,3411,3064,5687,9695,774,6742,1170,898,8481,8875,6513,838,3440,8657,6398,1363,7782,9118,4259,1213,5104,8726,6902,8138,6035,4384,4625,4988,227,6835,4966,6526,6738,1977,6546
9788:   1223 μs
7110:   103376 μs
8401:   81 μs
3277:   31 μs
5012:   52 μs
9792:   32 μs
5187:   32 μs
5243:   25 μs
9454:   27 μs
9768:   56 μs
6704:   29 μs
7515:   35 μs
5221:   38 μs
FALSE POSITIVE!!! Value: 7194
7194:   102545 μs
9926:   147 μs
8272:   77 μs
8259:   71 μs
2216:   103 μs
3199:   66 μs
9515:   45 μs
4441:   37 μs
8665:   70 μs
2957:   100 μs
1895:   3484 μs
9574:   116 μs
1758:   75 μs
6829:   67 μs
FALSE POSITIVE!!! Value: 9497
9497:   100520 μs
9709:   50 μs
FALSE POSITIVE!!! Value: 4811
4811:   100323 μs
FALSE POSITIVE!!! Value: 7938
7938:   100478 μs
7709:   181 μs
2854:   79 μs
6373:   55 μs
5014:   100247 μs
6076:   160 μs
5746:   146 μs
33:     288 μs
7447:   100554 μs
7782:   100274 μs
7500:   100358 μs
3222:   194 μs
2283:   70 μs
633:    78 μs
7454:   79 μs
3692:   62 μs
FALSE POSITIVE!!! Value: 4013
4013:   100236 μs
2317:   51 μs
1829:   11 μs
804:    12 μs
1346:   30 μs
False Positive Ratio: 0.16504636923404759

Lots of False Positive occurred this time. It’s about 16%.