TextGrid.seedFillOld takes considerable amount of time

[ggrossetie]

The following diagram takes more than 30 seconds to produce an image:

                                                                           +-------------------+
                                                                           |  ABCD_RSTAR_MAIL  |
                                                                           | [ABCD_RSTAR_MAIL] |
                                                                           +-------------------+
                                                                                     |
  PROCESS_ALL_APPLICATIONS (//) -> subStep.each(createPod)                           V
 +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 |                                                                                   ||                                                                                                          |
 |                                                                                   || <application, packname, installeurDir>                                                                   |
 |  PROCESS_APPLICATION (+) -> each(applicationsList)                                \/                                                                                                          |
 | +-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ |
 | |                                                                                 |                                                                                                         | |
 | |                                                                                 |                                                                                                         | |
 | |            PROCESS_PREPARE_INSTALL (//)                                         V                                                                                                         | |
 | |           +----------------------------------------------------------------------------------------------------------------------------------------------------------+                    | |
 | |           |                          ||                                                                                   ||                                         |                    | |
 | |           |                          ||                                                                                   ||                                         |                    | |
 | |           |                          \/                                                   PROCESS_PREPARE_INSTALLEUR (+)  \/                                         |                    | |
 | |           |          +-----------------------------------------------+                   +----------------------------------------------------------+                |                    | |
 | |           |          |          GENERATE_PACK                        |                   |                            |                             |                |                    | |
 | |           |          | [INSTALL_APPS, INSTALL_BATCHS, GENERATE_PACK] |                   |                            |                             |                |                    | |
 | |           |          +-----------------------------------------------+                   |                            V                             |                |                    | |
 | |           |                          ||                                                  | +------------------------------------------------------+ |                |                    | |
 | |           |                          ||                                                  | |                      GET_INSTALLEUR                  | |                |                    | |
 | |           |                          ||                                                  | | [ INSTALL_EXSTR, CALL_TILOGFHSQZ_ENV, INSTALL_OTLLS] | |                |                    | |
 | |           |                          ||                                                  | +------------------------------------------------------+ |                |                    | |
 | |           |                          ||                                                  |                            |                             |                |                    | |
 | |           |                          ||                                                  |                            |                             |                |                    | |
 | |           |                          ||                                                  |                            V                             |                |                    | |
 | |           |                          ||                                                  |  +----------------------------------------------------+  |                |                    | |
 | |           |                          ||                                                  |  |                    GET_CONFIG                      |  |                |                    | |
 | |           |                          ||                                                  |  |       [ CALL_DGHUYLOMPR_STATUS_DEACTIVATE ]        |  |                |                    | |
 | |           |                          ||                                                  |  |  [ INSTALL_APPS, INSTALL_BATCHS, INSTALL_EXSTR ]   |  |                |                    | |
 | |           |                          ||                                                  |  |    [ COPY_RESOURCES_WEB, CALL_TILOGFHSQZ_ENV ]     |  |                |                    | |
 | |           |                          ||                                                  |  | [ CALL_DGHUYLOMPR_STATUS_ACTIVATE, INSTALL_OTLLS ] |  |                |                    | |
 | |           |                          ||                                                  |  +----------------------------------------------------+  |                |                    | |
 | |           |                          ||                                                  |                            |                             |                |                    | |
 | |           |                          ||                                                  |                            |                             |                |                    | |
 | |           |                          ||                                                  |                            V                             |                |                    | |
 | |           |                          ||                                                  +----------------------------------------------------------+                |                    | |
 | |           |                          ||                                                                               ||                                             |                    | |
 | |           |                          ||                                                                               ||                                             |                    | |
 | |           |                          \/                                                                               \/                                             |                    | |
 | |           +----------------------------------------------------------------------------------------------------------------------------------------------------------+                    | |
 | |                                                                                 |                                                                                                         | |
 | |                                                                                 |                                                                                                         | |
 | |            PROCESS_INIT_INSTALL (//)                                            V                                                                                                         | |
 | |           +-------------------------------------------------------------------------------------------------------------------------------------------+                                   | |
 | |           |                 ||                                       ||                                                    ||                         |                                   | |
 | |           |                 ||                                       ||                                                    ||                         |                                   | |
 | |           |                 \/                                       \/                                                    \/                         |                                   | |
 | |           | +--------------------------------+    +-------------------------------------+    +------------------------------------------------------+ |                                   | |
 | |           | |            GET_PACK            |    |       DEACTIVATE_ENV_DGHUYLOMPR     |    |                    EXEC_INSTALLEUR                   | |                                   | |
 | |           | | [INSTALL_APPS, INSTALL_BATCHS] |    | [CALL_DGHUYLOMPR_STATUS_DEACTIVATE] |    | [ INSTALL_EXSTR, CALL_TILOGFHSQZ_ENV, INSTALL_OTLLS] | |                                   | |
 | |           | +--------------------------------+    +-------------------------------------+    +------------------------------------------------------+ |                                   | |
 | |           |                 ||                                       ||                                                    ||                         |                                   | |
 | |           |                 ||                                       ||                                                    ||                         |                                   | |
 | |           |                 \/                                       \/                                                    \/                         |                                   | |
 | |           +-------------------------------------------------------------------------------------------------------------------------------------------+                                   | |
 | |                                                                                 |                                                                                                         | |
 | |                                                                                 |                                                                                                         | |
 | |  PROCESS_INSTALL (//)                                                           V                                                                                                         | |
 | | +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ | |
 | | |                               || <nodeType=batchs>     ||                            ||                          ||                              ||                                   | | |
 | | |                               ||                       ||                            ||                          ||                              ||                                   | | |
 | | |  PROCESS_INSTALL_BATCHS (//)  \/  [ INSTALL_BATCHS ]   ||  PROCESS_INSTALL_APPS (//) \/  [ INSTALL_APPS ]        ||   PROCESS_INSTALL_EXSTR (+)  \/  [ INSTALL_EXSTR ]                | | |
 | | | +----------------------------------------------------+ || +-----------------------------------------------+      ||  +-------------------------------------------------------------+  | | |
 | | | |                                 ||                 | || |                               ||              |      ||  |                           |                                 |  | | |
 | | | | PROCESS_INSTALL_BATCHS_NODE (+) \/                 | || | PROCESS_INSTALL_APPS_NODE (+) \/              |      ||  |                           |                                 |  | | |
 | | | | +------------------------------------------------+ | || | +-------------------------------------------+ |      ||  |                           V                                 |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  |                 +----------------+                          |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  |                 | INSTALL_EXSTR  |                          |  | | |
 | | | | |                         V                      | | || | |                     V                     | |      ||  |                 +----------------+                          |  | | |
 | | | | |                  +-------------+               | | || | |               +-----------+               | |      ||  |                           |                                 |  | | |
 | | | | |                  | STOP_BATCHS |               | | || | |               | STOP_APPS |               | |      ||  |                           |                                 |  | | |
 | | | | |                  +-------------+               | | || | |               +-----------+               | |      ||  |                           V                                 |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  +-------------------------------------------------------------+  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||                                                                   | | |
 | | | | |                         V                      | | || | |                     V                     | |      ||                                                                   | | |
 | | | | |               +------------------+             | | || | |            +----------------+             | |      ||                                                                   | | |
 | | | | |               | UNINSTALL_BATCHS |             | | || | |            | UNINSTALL_APPS |             | |      ||                                                                   | | |
 | | | | |               +------------------+             | | || | |            +----------------+             | |      ||                                                                   | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||                                                                   | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||                                                                   | | |
 | | | | |                         V                      | | || | |                     V                     | |      ||                                                                   | | |
 | | | | |                +----------------+              | | || | |             +--------------+              | |      ||___________________________________________                        | | |
 | | | | |                | INSTALL_BATCHS |              | | || | |             | INSTALL_APPS |              | |      ||------------------------------------------ |                       | | |
 | | | | |                +----------------+              | | || | |             +--------------+              | |      ||                                          ||                       | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||                                          ||                       | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||   PROCESS_INSTALL_RESOURCES_WEB_HELP (+) \/[ COPY_RESOURCES_WEB ] | | |
 | | | | |                         V                      | | || | |                     V                     | |      ||  +-------------------------------------------------------------+  | | |
 | | | | |                +----------------+              | | || | |              +------------+               | |      ||  |                              |                              |  | | |
 | | | | |                | STATUS_BATCHS  |              | | || | |              | RSTAR_APPS |               | |      ||  |                              |                              |  | | |
 | | | | |                +----------------+              | | || | |              +------------+               | |      ||  |                              V                              |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  |                   +-------------------------+               |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  |                   | GET_RESOURCES_WEB_HELP  |               |  | | |
 | | | | |                         |                      | | || | |                     V                     | |      ||  |                   +-------------------------+               |  | | |
 | | | | |                         |                      | | || | |              +-------------+              | |      ||  |                              |                              |  | | |
 | | | | |                         |                      | | || | |              | STATUS_APPS |              | |      ||  |                              |                              |  | | |
 | | | | |                         |                      | | || | |              +-------------+              | |      ||  |                              V                              |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  |                   +-------------------------+               |  | | |
 | | | | |                         |                      | | || | |                     |                     | |      ||  |                   | COPY_RESOURCES_WEB_HELP |               |  | | |
 | | | | +------------------------------------------------+ | || | +-------------------------------------------+ |      ||  |                   +-------------------------+               |  | | |
 | | | |                           |                        | || |                       |                       |      ||  |                              |                              |  | | |
 | | | |                           V                        | || |                       V                       |      ||  |                              V                              |  | | |
 | | | +---------------------------+------------------------+ || +-----------------------------------------------+      ||  +-------------------------------------------------------------+  | | |
 | | |                                                        ||                                                        ||                                                                   | | |
 | | |                                                        ||                                                        ||                                                                   | | |
 | | |                                                        ||                                                        ||                                                                   | | |
 | | |                                                        ||                                                        ||                                                                   | | |
 | | |                                                        ||                                                        ||                                                                   | | |
 | | |                                                        ||                                                        ||                                                                   | | |
 | | |                           PROCESS_INSTALL_${tool} (+)  \/ [ INSTALL_OTLLS ]   PROCESS_INSTALL_RESOURCES_WEB (+)  \/  [ COPY_RESOURCES_WEB ]                                           | | |
 | | |                          +-------------------------------------------------+ +-------------------------------------------------------------+                                          | | |
 | | |                          |                         |                       | |                              |                              |                                          | | |
 | | |                          |                         |                       | |                              |                              |                                          | | |
 | | |                          |                         V                       | |                              V                              |                                          | | |
 | | |                          |            +-------------------------+          | |                   +--------------------+                    |                                          | | |
 | | |                          |            | GET_TOOL_CONFIG_${tool} |          | |                   | GET_RESOURCES_WEB  |                    |                                          | | |
 | | |                          |            +-------------------------+          | |                   +--------------------+                    |                                          | | |
 | | |                          |                         |                       | |                              |                              |                                          | | |
 | | |                          |                         |                       | |                              |                              |                                          | | |
 | | |                          |                         V                       | |                              V                              |                                          | | |
 | | |                          |                +-----------------+              | |                   +--------------------+                    |                                          | | |
 | | |                          |                | INSTALL_${tool} |              | |                   | COPY_RESOURCES_WEB |                    |                                          | | |
 | | |                          |                +-----------------+              | |                   +--------------------+                    |                                          | | |
 | | |                          |                         |                       | |                              |                              |                                          | | |
 | | |                          |                         V                       | |                              V                              |                                          | | |
 | | |                          +-------------------------------------------------+ +-------------------------------------------------------------+                                          | | |
 | | |                                                       ||                                                    ||                                                                        | | |
 | | |                                                       ||                                                    ||                                                                        | | |
 | | |                                                       \/                                                    \/                                                                        | | |
 | | +-----------------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------+ | |
 | |                                                                                     |                                                                                                     | |
 | |                                                                                     |                                                                                                     | |
 | |                                                                                     V                                                                                                     | |
 | |                                                                        +------------------------+                                                                                         | |
 | |                                                                        | DELIVER_ENV_DGHUYLOMPR |                                                                                         | |
 | |                                                                        | [CALL_TILOGFHSQZ_ENV]  |                                                                                         | |
 | |                                                                        +------------------------+                                                                                         | |
 | |                                                                                     |                                                                                                     | |
 | |                                                                                     |                                                                                                     | |
 | |                                                                                     V                                                                                                     | |
 | |                                                                  +------------------+------------------+                                                                                  | |
 | |                                                                  |       ACTIVATE_ENV_DGHUYLOMPR       |                                                                                  | |
 | |                                                                  |  [CALL_DGHUYLOMPR_STATUS_ACTIVATE]  |                                                                                  | |
 | |                                                                  +-------------------------------------+                                                                                  | |
 | |                                                                                     |                                                                                                     | |
 | |                                                                                     |                                                                                                     | |
 | |                                                                                     V                                                                                                     | |
 | +-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ |
 |                                                                                       ||                                                                                                      |
 |                                                                                       ||                                                                                                      |
 |                                                                                       \/                                                                                                      |
 +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
                                                                                         |
                                                                                         |
                                                                                         V
                                                                        +--------------------------------+
                                                                        |          TAG_REF_CONFIG        |
                                                                        | [INSTALL_APPS, INSTALL_BATCHS] |
                                                                        +--------------------------------+
                                                                                         |
                                                                                         |
                                                                                         V
                                                                                +-----------------+
                                                                                |  ABCD_END_MAIL  |
                                                                                | [ABCD_END_MAIL] |
                                                                                +-----------------+

Here's the flamegraph:

As you can see 80% of the time is spent in the TextGrid.seedFillOld method:

ditaa/src/java/org/stathissideris/ascii2image/text/TextGrid.java

Lines 1354 to 1383 in f2286c4

	private CellSet seedFillOld(Cell seed, char newChar){
	CellSet cellsFilled = new CellSet();
	char oldChar = get(seed);
	if(oldChar == newChar) return cellsFilled;
	if(isOutOfBounds(seed)) return cellsFilled;
	Stack<Cell> stack = new Stack<Cell>();
	stack.push(seed);
	while(!stack.isEmpty()){
	Cell cell = (Cell) stack.pop();
	set(cell, newChar);
	cellsFilled.add(cell);
	Cell nCell = cell.getNorth();
	Cell sCell = cell.getSouth();
	Cell eCell = cell.getEast();
	Cell wCell = cell.getWest();
	if(get(nCell) == oldChar) stack.push(nCell);
	if(get(sCell) == oldChar) stack.push(sCell);
	if(get(eCell) == oldChar) stack.push(eCell);
	if(get(wCell) == oldChar) stack.push(wCell);
	}
	return cellsFilled;
	}

I'm not familiar with the code base but maybe it can be optimized?

Let me know if you need more information, I will gladly provide them 🤗

[ggrossetie]

Using an ArrayList instead of an HashSet divide time by 2.5.
I didn't spot any visual difference and other diagrams seem to run as fast as before.

If needed, we could probably remove duplicates once seedFillOld is completed?

[stathissideris]

Hello, thanks for looking into this. By this point I'm also unfamiliar with the code (haven't touched it for ages!) but I'm wondering whether seedFill is equivalent to seedFillOld but faster. seedFill is not being used in the code at all, and the naming implies that I was going to replace the "old" method with the new one. Would you like to switch to the new one and see if it's correct/faster?

[ggrossetie]

Hello @stathissideris!

Thanks for you reply.

When using seedFill the process seems to run in an infinite loop (inside fillCellsWith) 😬
But even if the implementation was correct, I doubt it would be any faster because what takes most of the time is HashSet.add and this line is present in both implementations:

seedFillOld

ditaa/src/java/org/stathissideris/ascii2image/text/TextGrid.java

Line 1369 in f2286c4

cellsFilled.add(cell);

seedFill

ditaa/src/java/org/stathissideris/ascii2image/text/TextGrid.java

Line 1338 in f2286c4

cellsFilled.add(cell);

Using TreeSet is considerably faster (17 seconds).
Since elements in a TreeSet are sorted, I was "forced" to implement Comparable:

@Override
public int compareTo(Cell o) {
  if (this.x == o.x) {
    return this.y - o.y;
  }
  return this.x - o.x;
}

Using ArrayList is still faster (10 seconds) but can contains duplicates.
Do you remember why/if using a Set is important in this context?

[ggrossetie]

Hello, thanks for looking into this. By this point I'm also unfamiliar with the code (haven't touched it for ages!)

@stathissideris I wonder if you would like to hand over or add more contributors to this project?

Pepijn has done great work (and fixed a couple of issues) on his fork: https://github.com/pepijnve/ditaa

PlantUML is using ditaa but there are some major issues (infinite loops, exceptions, inefficient code) that can be used as a Denial of Service (DoS) attack.
So if you don't plan to work on ditaa anymore maybe we should plan the transition so that PlantUML can migrate to an active fork? What do you think?

[hohle]

I understand this won't be merged, but the HashSet isn't really the issue, the #hashCode method TextGrid.Cell is. I changed the implementation to Szudzik's Elegant Pairing and saw significant speedup. I haven't looked at Pepijn's branch yet, but I'm also accumulating a bunch of refactoring and performance enhancements in a local branch that I may push sometime in the future.