Last active
October 1, 2025 15:01
-
-
Save renggli/2d3b91053c8e2bc031a6b5a256f8ed53 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // ignore_for_file: depend_on_referenced_packages | |
| import 'dart:io'; | |
| import 'dart:math'; | |
| import 'package:collection/collection.dart'; | |
| import 'package:xml/src/xpath/evaluation/sort.dart'; | |
| import 'package:xml/xml.dart'; | |
| import 'benchmark.dart'; | |
| XmlDocument createFlatDocument(int size) => XmlDocument([ | |
| XmlElement.tag( | |
| 'root', | |
| children: [for (int i = 0; i < size; i++) XmlElement.tag('item_$i')], | |
| ), | |
| ]); | |
| XmlDocument createDeepDocument(int size) { | |
| final root = XmlElement.tag('root'); | |
| var current = root; | |
| for (var i = 0; i < size; i++) { | |
| current.children.add(current = XmlElement.tag('item_$i')); | |
| } | |
| return XmlDocument([root]); | |
| } | |
| XmlDocument createMixedDocument(int size) { | |
| final root = XmlElement.tag('root'); | |
| for (var i = 0; i < sqrt(size).floor(); i++) { | |
| var current = root; | |
| for (var j = 0; j < sqrt(size).floor(); j++) { | |
| current.children.add(current = XmlElement.tag('item_${i}_$j')); | |
| } | |
| } | |
| return XmlDocument([root]); | |
| } | |
| XmlDocument createPolluted(XmlDocument document) { | |
| final copy = document.copy(); | |
| for (final node in document.descendantElements) { | |
| node.attributes.add(XmlAttribute(XmlName('pollution'), '')); | |
| node.children.add(XmlElement.tag('pollution')); | |
| } | |
| return copy; | |
| } | |
| void main(List<String> args) { | |
| for (final size in [5, 10, 50, 100, 1000, 10000]) { | |
| for (final (documentName, document) in [ | |
| ('flat', createFlatDocument(size)), | |
| ('deep', createDeepDocument(size)), | |
| ('mixed', createMixedDocument(size)), | |
| ]) { | |
| for (final (pollutedName, polluted) in [ | |
| ('clean', document), | |
| // Stack-overflow when the document is too deep. | |
| if (size <= 1000 || documentName != 'deep') | |
| ('polluted', createPolluted(document)), | |
| ]) { | |
| final ordered = polluted.rootElement.descendantElements | |
| .where((node) => node.name.qualified.startsWith('item_')) | |
| .toList(); | |
| final reversed = ordered.toList()..reverseRange(0, ordered.length); | |
| final shuffled = ordered.toList()..shuffleRange(0, ordered.length); | |
| for (final (orderName, nodes) in [ | |
| ('ordered', ordered), | |
| ('reversed', reversed), | |
| ('shuffled', shuffled), | |
| ]) { | |
| final standard = benchmark( | |
| () => nodes.toList().sort((a, b) => a.compareNodePosition(b)), | |
| ); | |
| final primitive = benchmark(() { | |
| final present = nodes.toList().toSet(); | |
| nodes.first.root.descendants.where(present.contains).toList(); | |
| }); | |
| final proposed = benchmark( | |
| () => nodes.toList().sortedInDocumentOrder(isUnique: true), | |
| ); | |
| stdout.writeln( | |
| [ | |
| size, | |
| documentName, | |
| pollutedName, | |
| orderName, | |
| standard.toStringAsFixed(6), | |
| primitive.toStringAsFixed(6), | |
| proposed.toStringAsFixed(6), | |
| ].join(';'), | |
| ); | |
| } | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment