Introduce the concept of isolated macros

Development
1

Hi everyone,

currently, in the macro transformation that executes all macros in the page, we search the whole XDOM for the macro block with the highest priority - and we do this again after executing a macro. The reason for this is that in theory macros have access to the whole XDOM, and thus they can add or remove macro blocks wherever they want. In practice, this rarely happens. In fact, most macros don’t even care about the order in which they’re executed.

If we knew more about the macros, there are two possible optimizations:

  1. Macros that guarantee that they’re fully isolated in the sense that their output only depends on the macro parameters and content (but not other elements present in the XDOM) and that don’t execute/transform their content could be executed in any order and as soon as we find them. This would apply to macros like id or code.
  2. We could keep a priority queue of all remaining macro blocks and only re-build the queue after executing a macro that doesn’t guarantee that it won’t modify the XDOM.

The problem of optimization 2 is that it’s only beneficial once most macros indicate that they’re safe and until then it could actually make the performance worse. While building a priority queue is cheap, it’s still more expensive than just iterating over the macros. There is in theory the possibility to automatically detect if the XDOM is modified, but this seems hard, too. As many macros should fall into category 1, I think this should bring us most benefits.

Therefore, I propose the following changes:

  1. Introduce a method boolean isExecutionIsolated(P parameters, String content) in org.xwiki.rendering.macro.Macro that returns false by default. It should return true if the execution is independent of the XDOM and doesn’t execute other macros.
  2. When iterating over the XDOM to find the next macro to execute, we ask every macro if the execution is isolated, and if yes, we immediately execute it, and then continue the iteration.

The rationale to pass the parameters is to allow, e.g., the HTML macro to return true if the wiki parameter is false. The macro transformation would cache the set of macros for whom isExecutionIsolated returned false in an IdentityHashMap to avoid calling the method again and again.

What I’m wondering about is if the HTML macro is really isolated, though, as its results depends on whether the context is restricted and if the context author has script right. And in theory, there could be a higher-priority macro that is executed before the isolated macro that changes this. I’m not sure whether this is really something we should consider, it’s just a thought.

Wiki macros seem to use their position in the XDOM to compute an ID and thus they’re not truly isolated: xwiki-platform/xwiki-platform-core/xwiki-platform-rendering/xwiki-platform-rendering-wikimacro/xwiki-platform-rendering-wikimacro-store/src/main/java/org/xwiki/rendering/wikimacro/internal/DefaultWikiMacroRenderer.java at c99d501ed41cbee6a3c02ff927714531570789de · xwiki/xwiki-platform · GitHub - we could ignore this and allow wiki macros do declare themselves as isolated with a new property in the wiki macro descriptor. In general, we would still execute isolated macros in-order, so I think the IDs should still be stable. However, even with the current code, I doubt these IDs are unique (a macro that is executed after the current macro could insert content in the XDOM before the current macro that has the same ID as the current macro), so I’m not really sure what the idea of using the index is.

Do you have any opinions on this?

2

+1

We need some stable way to identify the macro call, and right now we don’t really have much more than the block index to do that.

3

+1

4

The problem I see is that this index isn’t stable as it depends on the execution of other macros. Imagine macros at index 50, and 100. First, we execute the macro A at index 100 as it has the highest priority. It gets index 100. Then we execute the macro B at index 50, it inserts 50 blocks into the XDOM including another macro A at the end at index 100. Then we execute the new macro A at index 100 which gets the exactly same ID as the first macro.

5

Sure, it’s not perfect in theory, but what you describe does not happen that much in practice, and again we don’t have much else to identify a macro among others in a XDOM.

6

We do have the content and the parameters of the macro that we could hash, and we could also hash the content and the parameters of all parent macros. To each of these, we could add the index in the children list. This should be pretty unique and if a collision should happen, you would at least know that the macro is basically the same (same parameters, same content).

7

I could imagine a macro giving a very different result depending on their location if they are taking into account blocks around them (like the toc macro).

8

+1

9

Some questions for my understanding:

Are macros which output things like e.g. {{html}} {{box}} or other macro calls isolated?

Is a macro which uses some values from the binding (e.g for generating different IDs of tables) isolated?

Will this concept guarantee that macro calls (with the same priority) are processed in the order in which theses appear in the source code?

10

I’ve noticed a problem with this approach: In theory, there could be a macro with a high priority (low priority value) that iterates over the XDOM and, e.g., changes all ID macros. While this seems unlikely, it would be a breaking change. I got a new, similar idea how to fix this, though:

  1. We introduce the method as mentioned before, but the condition is weakened to that the macro must not modify the XDOM, which includes that the macro must not execute arbitrary macros with access to the XDOM as they could modify the XDOM. So in contrast to what I proposed before, macros would be allowed to read the XDOM.
  2. In the macro transformation, instead of getting the first macro with the lowest priority number, we get all macros of the lowest priority number in a Deque. Until this Deque is empty, we repeate the following:
    1. We check if the macro execution of the first macro in the queue is isolated.
    2. We execute the first macro in the queue and remove it from the queue.
    3. If the macro execution is isolated, we scan the blocks in the result of the macro execution and extract a queue of the macros with the lowest priority number.
      1. If the priority number is higher than the priority of the current queue, we discard the new queue (in fact, I would probably pass a parameter to avoid collecting them in the first place).
      2. If the priority is the same as the priority of the current queue, we add them to the front of the queue.
      3. If the priority is lower than the current queue, we replace the current queue by that new queue.
    4. If the macro execution isn’t isolated, we re-scan the whole XDOM to get a new queue.

I haven’t benchmarked this, but I assume that generating a queue instead of getting just the first element shouldn’t be noticeably more expensive in Java, in particular if we re-use the queue so the underlying array(s) don’t need to be re-allocated. In contrast to this, building a full priority queue would be more expensive as it needs additional comparison operations and swaps of elements.

With this updated proposal, I think we should get pretty much the same or even more benefits than with the first proposal (as more macros can be marked as isolated), and at the same time, we guarantee that all macros will be executed in the same order as before.

In general, yes, except the HTML can’t be considered as isolated when the wiki parameter is true, as the HTML macro executes macro transformations on its content with the full XDOM available to the macros so it cannot control if any of those macros in its content modify the XDOM. In contrast, while the box macro parses its content, it doesn’t execute transformations on it.

With my new proposal, yes. The idea before was already to execute them in the order of the tree, so in the order where they are found, but I agree that this creates quite a few difficult cases and I think the new proposal should be much more robust in this case.

Btw., just for context, what I’m trying to optimize here as example is a long page with about 5k macros, among them 3.4k code macros and 850 ID macros that currently takes 28 seconds to execute on a cloud server (8.5 seconds locally on a laptop), where about 70% of the running time is spent in the code that gets the next macro to execute.

11

+1 for that approach, as it seems more suited to avoid breaking changes.

12

+1 for the new idea too

13

I’ve implemented this with an actual priority queue now as otherwise I observed way too frequent re-scans due to the nesting of high-priority macros in lower-priority macros. The priority queue causes some overhead, but even in what I would consider a worst-case situation (5k non-isolated macros in the original XDOM), it was only like 20ms.

I’ve also added a configuration option to mark a macro as isolated as discussed in the pull request which should greatly help to apply this easily without changing all macros.

I’ve merged the changes as part of XRENDERING-778, and they will be part of XWiki 17.3.0RC1. I plan a backport to XWiki 16.10.x at a later date when we’ve tested these changes a bit more.

1 Like
14

Thx @MichaelHamann for working on this!