比较两个“Uint8List”相等性的正确快速方法是什么？

Question

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

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

作为基准，一个纯 C 程序在同一系统上调用memcmp相同大小的字节数组 ( ) 大约需要 0.011 秒。clang -O3 memcmp_test.c && a.out

对于dart:ffi，不幸的是目前无法传递 aUint8List，因此必须首先将现有的Uint8List复制到 C 内存缓冲区。对于大量数据，额外的分配和复制将主导运行时成本。然而，如果您一开始就进行了适当的分配Pointer<Uint8>，并在需要将其传递给 Dart 代码时使用.asTypedList，那么运行时成本应该与memcmp.