commonmark / commonmark/commonmark.js

Optimize tight/loose list parsing (new algorithm from commonmark-java)

Open
#151 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
JavaScript
Stars
1.6k
Forks
231
Avg merge
2d 11h
Merged PRs (30d)
3

Description

Hey! The commonmark-java implementation was using the same algorithm as commonmark.js and cmark for determining whether a list is tight or loose. I recently re-implemented it because it showed up in a profiling session.

The results for the new algorithm are pretty good: a 10% performance improvement! See details here: https://github.com/atlassian/commonmark-java/commit/cfd28faa221056a1a28ce402ed8a278afe9e527d

I'm opening this issue because you might be interested in porting it back to the reference implementations :). I don't know if the improvement will be as significant, but it's worth a try.

It works like this (but see the commit above for details):

  • In the parser for list items:
    • in continue, remember when there was a blank line (except when a code block is being parsed)
    • in canContain (which is called when a new child will be added), set tight to false if we saw a blank line before
  • In the parser for list blocks:
    • in continue, remember when we had a blank line (and how many lines back it was)
    • in canContain, set tight to false if the previous line was blank

(The new algorithm also feels simpler, hopefully there's no holes in it. It passes all the spec tests and some extra ones.)

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading the linked commonmark-java commit and locating the list-item and list-block parser methods named in the issue: continue and canContain. Trace how blank lines currently affect tightness, then compare the proposed state tracking with the existing implementation. Run the CommonMark spec tests and confirm that list-tightness behavior is unchanged while performance improves.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
tooling
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.