dart linked list ffi benchmark

main.dart

// ignore_for_file: avoid_print

import 'dart:ffi' as ffi;

import 'package:benchmark_harness/benchmark_harness.dart';
import 'package:ffi/ffi.dart';

// ============================================================================
// Pure Dart LinkedList Implementation
// ============================================================================

class DartNode {
  DartNode(this.value);
  int value;
  DartNode? next;
}

class DartLinkedList {
  DartNode? _head;
  int _length = 0;

  void add(int value) {
    final node = DartNode(value);
    if (_head == null) {
      _head = node;
    } else {
      var current = _head!;
      while (current.next != null) {
        current = current.next!;
      }
      current.next = node;
    }
    _length++;
  }

  int? find(int value) {
    var current = _head;
    var index = 0;
    while (current != null) {
      if (current.value == value) {
        return index;
      }
      current = current.next;
      index++;
    }
    return null;
  }

  void clear() {
    _head = null;
    _length = 0;
  }

  int get length => _length;
}

// ============================================================================
// FFI LinkedList Implementation
// ============================================================================

// Native Node structure
final class NativeNode extends ffi.Struct {
  @ffi.Int64()
  external int value;

  external ffi.Pointer<NativeNode> next;
}

class FfiLinkedList {
  ffi.Pointer<NativeNode>? _head;
  int _length = 0;

  void add(int value) {
    final node = calloc<NativeNode>();
    node.ref.value = value;
    node.ref.next = ffi.nullptr;

    if (_head == null) {
      _head = node;
    } else {
      var current = _head!;
      while (current.ref.next != ffi.nullptr) {
        current = current.ref.next;
      }
      current.ref.next = node;
    }
    _length++;
  }

  int? find(int value) {
    if (_head == null) return null;

    var current = _head!;
    var index = 0;
    while (current != ffi.nullptr) {
      if (current.ref.value == value) {
        return index;
      }
      current = current.ref.next;
      index++;
    }
    return null;
  }

  void clear() {
    if (_head == null) return;

    var current = _head!;
    while (current != ffi.nullptr) {
      final next = current.ref.next;
      calloc.free(current);
      current = next;
    }
    _head = null;
    _length = 0;
  }

  int get length => _length;

  void dispose() {
    clear();
  }
}

// ============================================================================
// Benchmarks
// ============================================================================

class DartLinkedListAddBenchmark extends BenchmarkBase {
  DartLinkedListAddBenchmark() : super('DartLinkedList.add');
  late DartLinkedList list;

  @override
  void setup() {
    list = DartLinkedList();
  }

  @override
  void run() {
    for (var i = 0; i < 1000; i++) {
      list.add(i);
    }
  }

  @override
  void teardown() {
    list.clear();
  }
}

class FfiLinkedListAddBenchmark extends BenchmarkBase {
  FfiLinkedListAddBenchmark() : super('FfiLinkedList.add');
  late FfiLinkedList list;

  @override
  void setup() {
    list = FfiLinkedList();
  }

  @override
  void run() {
    for (var i = 0; i < 1000; i++) {
      list.add(i);
    }
  }

  @override
  void teardown() {
    list.dispose();
  }
}

class DartLinkedListFindBenchmark extends BenchmarkBase {
  DartLinkedListFindBenchmark() : super('DartLinkedList.find');
  late DartLinkedList list;

  @override
  void setup() {
    list = DartLinkedList();
    for (var i = 0; i < 1000; i++) {
      list.add(i);
    }
  }

  @override
  void run() {
    for (var i = 0; i < 1000; i++) {
      list.find(i);
    }
  }

  @override
  void teardown() {
    list.clear();
  }
}

class FfiLinkedListFindBenchmark extends BenchmarkBase {
  FfiLinkedListFindBenchmark() : super('FfiLinkedList.find');
  late FfiLinkedList list;

  @override
  void setup() {
    list = FfiLinkedList();
    for (var i = 0; i < 1000; i++) {
      list.add(i);
    }
  }

  @override
  void run() {
    for (var i = 0; i < 1000; i++) {
      list.find(i);
    }
  }

  @override
  void teardown() {
    list.dispose();
  }
}

class DartLinkedListMixedBenchmark extends BenchmarkBase {
  DartLinkedListMixedBenchmark() : super('DartLinkedList.mixed');
  late DartLinkedList list;

  @override
  void setup() {
    list = DartLinkedList();
  }

  @override
  void run() {
    // Add 100 elements
    for (var i = 0; i < 100; i++) {
      list.add(i);
    }
    // Find 50 elements
    for (var i = 0; i < 50; i++) {
      list.find(i);
    }
  }

  @override
  void teardown() {
    list.clear();
  }
}

class FfiLinkedListMixedBenchmark extends BenchmarkBase {
  FfiLinkedListMixedBenchmark() : super('FfiLinkedList.mixed');
  late FfiLinkedList list;

  @override
  void setup() {
    list = FfiLinkedList();
  }

  @override
  void run() {
    // Add 100 elements
    for (var i = 0; i < 100; i++) {
      list.add(i);
    }
    // Find 50 elements
    for (var i = 0; i < 50; i++) {
      list.find(i);
    }
  }

  @override
  void teardown() {
    list.dispose();
  }
}

// ============================================================================
// Main
// ============================================================================

void main() {
  print('=' * 80);
  print('LinkedList Performance Comparison: Pure Dart vs FFI');
  print('=' * 80);
  print('');

  // Warmup
  print('Warming up...');
  final warmupDart = DartLinkedList();
  final warmupFfi = FfiLinkedList();
  for (var i = 0; i < 100; i++) {
    warmupDart.add(i);
    warmupFfi.add(i);
  }
  warmupDart.clear();
  warmupFfi.dispose();
  print('');

  // Run benchmarks
  print('Running benchmarks...');
  print('');

  print('--- Add Operations (1000 elements) ---');
  DartLinkedListAddBenchmark().report();
  FfiLinkedListAddBenchmark().report();
  print('');

  print('--- Find Operations (1000 searches in 1000 elements) ---');
  DartLinkedListFindBenchmark().report();
  FfiLinkedListFindBenchmark().report();
  print('');

  print('--- Mixed Operations (100 adds + 50 finds) ---');
  DartLinkedListMixedBenchmark().report();
  FfiLinkedListMixedBenchmark().report();
  print('');

  print('=' * 80);
  print('Benchmark complete!');
  print('=' * 80);
}