android - 比较两个 `Uint8List` 是否相等的正确快速方法是什么？

Question

给定 Uint8List a = ...; Uint8List b = ...; 我想比较它们的内容是否相同。当然，我可以在 Flutter 中使用 listEquals，或者写下一个简单的循环，例如:

for (int index = 0; index < a.length; index += 1) {
    if (a[index] != b[index])
      return false;
  }

但是，考虑到 Uint8List 是一个非常特殊的数组，而且它通常非常大，我想哪里有更好(更快)的方法来做到这一点？

Answer 1

我认为您应该能够通过一次比较 4 或 8 个字节来获得一些轻微的加速(这也应该有对齐的好处)。这应该不需要复制字节数据，因此不会有显着的内存损失。我写了一个快速实现来尝试一下:

import 'dart:typed_data';
import 'dart:math' show Random;

/// Naive [List] equality implementation.
bool listEquals<E>(List<E> list1, List<E> list2) {
  if (identical(list1, list2)) {
    return true;
  }

  if (list1.length != list2.length) {
    return false;
  }

  for (var i = 0; i < list1.length; i += 1) {
    if (list1[i] != list2[i]) {
      return false;
    }
  }

  return true;
}

/// Compares two [Uint8List]s by comparing 8 bytes at a time.
bool memEquals(Uint8List bytes1, Uint8List bytes2) {
  if (identical(bytes1, bytes2)) {
    return true;
  }

  if (bytes1.lengthInBytes != bytes2.lengthInBytes) {
    return false;
  }

  // Treat the original byte lists as lists of 8-byte words.
  var numWords = bytes1.lengthInBytes ~/ 8;
  var words1 = bytes1.buffer.asUint64List(0, numWords);
  var words2 = bytes2.buffer.asUint64List(0, numWords);

  for (var i = 0; i < words1.length; i += 1) {
    if (words1[i] != words2[i]) {
      return false;
    }
  }

  // Compare any remaining bytes.
  for (var i = words1.lengthInBytes; i < bytes1.lengthInBytes; i += 1) {
    if (bytes1[i] != bytes2[i]) {
      return false;
    }
  }

  return true;
}

void main() {
  var random = Random();

  // Generate random data.
  //
  // 100 MB minus a few bytes to avoid being an exact multiple of 8 bytes.
  const numBytes = 100 * 1000 * 1000 - 3;
  var data = Uint8List.fromList([
    for (var i = 0; i < numBytes; i += 1) random.nextInt(256),
  ]);

  var dataCopy = Uint8List.fromList(data);

  var stopwatch = Stopwatch()..start();
  var result = listEquals(data, dataCopy);
  print('Naive:     $result ${stopwatch.elapsed}');

  stopwatch
    ..reset()
    ..start();
  result = memEquals(data, dataCopy);
  print('memEquals: $result ${stopwatch.elapsed}');

我在我的 64 位 Linux 机器上将它作为 Dart 控制台应用程序运行的经验结果 (dart mem_equals.dart):

Naive:     true 0:00:00.152984
memEquals: true 0:00:00.038664

从编译它(dart compile exe mem_equals.dart && mem_equals.exe):

Naive:     true 0:00:00.093478
memEquals: true 0:00:00.033560

我没有与使用 dart:ffi 进行比较，但作为基准，纯 C 程序在相同大小的字节数组上调用 memcmp (clang -O3 memcmp_test.c && a.out) 在同一系统上大约需要 0.011s。