[PR #288] [MERGED] Rewrite Descendants iteratively #920

New Issue

claunia · 2026-01-29T14:47:17Z

claunia commented

2026-01-29 14:47:17 +00:00

📋 Pull Request Information

Original PR: https://github.com/xoofx/markdig/pull/288
Author: @MihaZupan
Created: 1/18/2019
Status: ✅ Merged
Merged: 1/19/2019
Merged by: @xoofx

Base: master ← Head: rewrite-descendants-search

📝 Commits (7)

1bbe20d Rewrite Descendants(MarkdownObject) iteratively
37325f1 Use existing Descantants(ContainerInline) implementation
4519d38 Rewrite Descendants(ContainerBlock) iteratively
282da04 Rewrite Descendants(ContainerInline) iteratively
f1b736f Add Test for Descendants order
b2a542b Simplify push condition
95cbf0e Cache Schema markdown in Tests

📊 Changes

5 files changed (+248 additions, -147 deletions)

View changed files

📝 src/Markdig.Tests/Markdig.Tests.csproj (+1 -0)
➕ src/Markdig.Tests/TestDescendantsOrder.cs (+85 -0)
📝 src/Markdig.Tests/TestParser.cs (+16 -0)
📝 src/Markdig/Syntax/Inlines/ContainerInline.cs (+28 -17)
📝 src/Markdig/Syntax/MarkdownObjectExtensions.cs (+118 -130)

📄 Description

I rewrote the Descendants extension methods to eliminate recursion. The order of returned elements is kept the same.

This comes with a significant memory allocation reduction when using Descendants over the entire AST like I do in my project.

Benchmarking between the recursive and iterative approaches I get this:

Iterative:

Method	Mean	Gen 0/1k Op	Gen 1/1k Op	Gen 2/1k Op	Allocated Memory/Op
Markdig	212.9 ms	99333.3333	-	-	74.89 MB
Markdig_Descendants	228.8 ms	98000.0000	2000.0000	-	78.22 MB

Recursive:

Method	Mean	Gen 0/1k Op	Gen 1/1k Op	Gen 2/1k Op	Allocated Memory/Op
Markdig	215.8 ms	99333.3333	-	-	74.89 MB
Markdig_Descendants	242.9 ms	98000.0000	119000.0000	6000.0000	104.3 MB

Where Markdig is only parsing to the AST while Markdig_Descendants parses to AST and loops over descendants once.

I have tested that the order is not modified when calling descending anywhere in the test suite.

I don't have tests for Descendants<T> of ContainerInline and ContainerBlock as they appear to not be used anywhere in Markdig itself, but I have included iterative implementations for those as well.

In the future, a few bytes could be shaved off by using ValueTuple instead of two stacks.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/xoofx/markdig/pull/288 **Author:** [@MihaZupan](https://github.com/MihaZupan) **Created:** 1/18/2019 **Status:** ✅ Merged **Merged:** 1/19/2019 **Merged by:** [@xoofx](https://github.com/xoofx) **Base:** `master` ← **Head:** `rewrite-descendants-search` --- ### 📝 Commits (7) - [`1bbe20d`](https://github.com/xoofx/markdig/commit/1bbe20dca1fdf7e81bbba981e41fc5fdb6068511) Rewrite Descendants(MarkdownObject) iteratively - [`37325f1`](https://github.com/xoofx/markdig/commit/37325f1bdcd7ab0678b842e66cf044badfdad71b) Use existing Descantants<T>(ContainerInline) implementation - [`4519d38`](https://github.com/xoofx/markdig/commit/4519d3820afa312141fb0550b80f426d56f95d66) Rewrite Descendants(ContainerBlock) iteratively - [`282da04`](https://github.com/xoofx/markdig/commit/282da043b767ca146496fd3cdc6845800629e03e) Rewrite Descendants(ContainerInline) iteratively - [`f1b736f`](https://github.com/xoofx/markdig/commit/f1b736f91825f289b60723e123b46f1a1195e1ec) Add Test for Descendants order - [`b2a542b`](https://github.com/xoofx/markdig/commit/b2a542b43e3a7598b5110c23e72771e082daaaea) Simplify push condition - [`95cbf0e`](https://github.com/xoofx/markdig/commit/95cbf0e6d21953967df042995e04d716510d4269) Cache Schema markdown in Tests ### 📊 Changes **5 files changed** (+248 additions, -147 deletions) <details> <summary>View changed files</summary> 📝 `src/Markdig.Tests/Markdig.Tests.csproj` (+1 -0) ➕ `src/Markdig.Tests/TestDescendantsOrder.cs` (+85 -0) 📝 `src/Markdig.Tests/TestParser.cs` (+16 -0) 📝 `src/Markdig/Syntax/Inlines/ContainerInline.cs` (+28 -17) 📝 `src/Markdig/Syntax/MarkdownObjectExtensions.cs` (+118 -130) </details> ### 📄 Description I rewrote the `Descendants` extension methods to eliminate recursion. **The order of returned elements is kept the same.** This comes with a significant memory allocation reduction when using `Descendants` over the entire AST like I do in my project. Benchmarking between the recursive and iterative approaches I get this: Iterative: | Method | Mean | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op | |-------------------- |---------:|------------:|------------:|------------:|--------------------:| | Markdig | 212.9 ms | 99333.3333 | - | - | 74.89 MB | | Markdig_Descendants | 228.8 ms | 98000.0000 | 2000.0000 | - | 78.22 MB | Recursive: | Method | Mean | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op | |-------------------- |---------:|------------:|------------:|------------:|--------------------:| | Markdig | 215.8 ms | 99333.3333 | - | - | 74.89 MB | | Markdig_Descendants | 242.9 ms | 98000.0000 | 119000.0000 | 6000.0000 | 104.3 MB | Where `Markdig` is only parsing to the AST while `Markdig_Descendants` parses to AST and loops over descendants once. I have tested that the order is not modified when calling descending anywhere in the test suite. I don't have tests for `Descendants<T>` of `ContainerInline `and `ContainerBlock `as they appear to not be used anywhere in Markdig itself, but I have included iterative implementations for those as well. In the future, a few bytes could be shaved off by using ValueTuple instead of two stacks. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

claunia added the pull-request label 2026-01-29 14:47:17 +00:00

claunia closed this issue

2026-01-29 14:47:18 +00:00

claunia referenced this issue

2026-01-29 14:52:56 +00:00

[PR #920] Support escaped quotes in generic attribute values #1308

Sign in to join this conversation.