fpdart sortBy is very slow and time processing scales very quickly

[hbock-42]

Sorting iterable with fpdart sortBy function can be very slow.

I understand the spirit of sorting using a functional programming style, but there is not a lot of benefit for the end user here.

For example, sorting a list of 2000 simple data using the same comparator:

• fpdart sortby: 2s04
• classic dart sort: 0s005

I understand that there is no sort function on iterable in the dart API. From what I understand, it is because any sort implementation on iterable would first convert the iterable to a list, then sort, then return the value, because sorting on an iterable is very slow.

I made a small benchmark.

I also proposed a solution to solve this problem without breaking fpdart API.

import 'package:fpdart/fpdart.dart';

void iterableListSortBench() {
  const bool printData = false;
  final int dataSetLength = 2000;
  final Iterable<FakeDataClass> iterableData = Iterable<FakeDataClass>.generate(
      dataSetLength, (index) => FakeDataClass(title: _titles[index % _titles.length], id: randomInt(0, 100).run()));
  final List<FakeDataClass> listData = List<FakeDataClass>.from(iterableData);
  fpdartSortIterableBench(iterableData, printData: printData);
  fpdartSortListBench(listData, printData: printData);
  sortListBench(listData, printData: printData);
  fastFpdartSortIterableBench(iterableData, printData: printData);
  fastFpdartSortListBench(listData, printData: printData);
}

void fpdartSortIterableBench(Iterable<FakeDataClass> it, {bool printData = false}) {
  print('start fpdart sort iterable bench');
  final sw = Stopwatch();
  sw.start();
  final sortedIt = it.fpdartSort;
  sw.stop();
  print('fpdart sort iterable:${sw.elapsed}');
  if (printData) {
    print(sortedIt.toStringWithNewLine());
  }
}

void fpdartSortListBench(List<FakeDataClass> li, {bool printData = false}) {
  print('start fp dart sort list bench');
  final sw = Stopwatch();
  sw.start();
  final sortedLi = li.fpdartSort;
  sw.stop();
  print('fpdart sort list:${sw.elapsed}');
  if (printData) {
    print(sortedLi.toStringWithNewLine());
  }
}

void sortListBench(List<FakeDataClass> li, {bool printData = false}) {
  print('start classic dart sort list bench');
  final sw = Stopwatch();
  sw.start();
  li.classicDartSort;
  sw.stop();
  print('classic dart sort list:${sw.elapsed}');
  if (printData) {
    print(li.toStringWithNewLine());
  }
}


void fastFpdartSortIterableBench(Iterable<FakeDataClass> it, {bool printData = false}) {
  print('start fast fpdart sort iterable bench');
  final sw = Stopwatch();
  sw.start();
  final sortedIt = it.fastFpdartSort(FakeDataClassOrder());
  sw.stop();
  print('fast fpdart sort iterable:${sw.elapsed}');
  if (printData) {
    print(sortedIt.toStringWithNewLine());
  }
}

void fastFpdartSortListBench(List<FakeDataClass> li, {bool printData = false}) {
  print('start fast fpdart sort list bench');
  final sw = Stopwatch();
  sw.start();
  final sortedLi = li.fastFpdartSort(FakeDataClassOrder());
  sw.stop();
  print('fast fpdart sort list:${sw.elapsed}');
  if (printData) {
    print(sortedLi.toStringWithNewLine());
  }
}

extension FakeDataIterableX on Iterable<FakeDataClass> {
  Iterable<FakeDataClass> get fpdartSort {
    final sorted = sortBy(FakeDataClassOrder());
    return sorted;
  }

  Iterable<FakeDataClass> fastFpdartSort(FakeDataClassOrder order) {
    final data = List<FakeDataClass>.from(this);
    data.sort((x, y) => order.compare(x, y));
    return data;
  }
}

extension FakeDataListX on List<FakeDataClass> {
  List<FakeDataClass> get fpdartSort {
    final sorted = sortBy(FakeDataClassOrder());
    return sorted.toList();
  }

  List<FakeDataClass> get classicDartSort {
    final data = List<FakeDataClass>.from(this);
    data.sort(fakeDataClassComparator);
    return data;
  }
}

class FakeDataClassOrder extends Order<FakeDataClass> {
  @override
  int compare(FakeDataClass x, FakeDataClass y) => fakeDataClassComparator(x, y);
}

int fakeDataClassComparator(FakeDataClass x, FakeDataClass y) {
  final titleDif = x.title.compareTo(y.title);
  return titleDif != 0 ? titleDif : x.id.compareTo(y.id);
}

class FakeDataClass {
  final String title;
  final int id;

  FakeDataClass({
    required this.title,
    required this.id,
  });

  @override
  String toString() => '$title\t$id';
}

const _titles = [
  'Hello',
  'ASOIMA',
  'dsakmdlkasm ',
  'He21d1',
  '12 12d 120id ',
  'asdas dasd ',
  ',asc as,sa',
  'asdowpo,',
  'cas, l,as l,',
  'apls,d o',
  'zsaxasd',
];

extension IterableX<E> on Iterable<E> {
  String toStringWithNewLine() {
    final data = this;
    return data.join('\n');
  }
}

[SandroMaglione]

Hi @hbock-42

Thanks for your benchmarks 🙏🏼

Indeed methods on List and Map in general would benefit from some refactoring and optimisation. We were discussing something similar in #65.

Feel free to open a PR with any update or improvement

[hbock-42]

@SandroMaglione Done! Minimal, but it is the first of a long series of contributions I hope

[SandroMaglione]

Thanks @hbock-42 🙏🏼