Skip to content

WIP: Dlist-ify recursive trees of list append computations

Carter Schonwald requested to merge wip/dlist into master

this is still WIP (collab between myself and with @typedrat, this work is 99% her )

its not quite ready, and @typedrat indicated that she wants to make sure some stuff is cleaned up before she Feels its ready.

Theres certainly plenty more to add after this chunk, but I figure better to start the dialogue sooner than later

context

in the course of some experiments around ways to improve parts of ghc core optimizer/rules etc, we noticed theres a lot of spots in ghc that recursively combine and flatten lists in a pattern which benefits from using DList style abstractions. Adding a vendored Dlist module implementation and changing those subsystems over to using dlist for that combining step changes possibly worst case quadratic computations into linear complexity ones.

This change set is the first in (hopefully ongoing) sequence of patches to

  1. move such computations over to dlist

  2. tighten up patterns of bad complexity in ghc. (we want faster code and faster compilers, AT THE SAME TIME :) )

some preliminary experiments showed that there was a large improvement in allcation numbers for a few parts of the test suite (notably a parsing input that historically brought ghc), and many tests have a 0.1-5% improvement.

checklist to address when removing WIP: tag

Thank you for your contribution to GHC!

Please take a few moments to verify that your commits fulfill the following:

  • are either individually buildable or squashed
  • have commit messages which describe what they do (referring to Notes and tickets using #NNNN syntax when appropriate)
  • have added source comments describing your change. For larger changes you likely should add a Note and cross-reference it from the relevant places.
  • add a testcase to the testsuite.
  • replace this message with a description motivating your change

If you have any questions don't hesitate to open your merge request and inquire in a comment. If your patch isn't quite done yet please do add prefix your MR title with WIP:.

Edited by Carter Schonwald

Merge request reports