issue-#72 speeding up the dump of large data structures

Post Reply
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

issue-#72 speeding up the dump of large data structures

Post by Josef Templ »

This issue is about an optimization in the generation of the post mortem dump of large data structures,
in particular for large arrays allocated on the stack. If such an array contains structured elements
(arrays or records) this involves a large number of StdFold.Flip operations, which in turn call the
TextModels.StdContext.Pos operation several times. The TextModels.StdContext.Pos operation
uses a linear search and the resulting runtime behavior is quadratic.

For the issue see http://redmine.blackboxframework.org/issues/72.

A proposal for a fix exists in CPC 1.7 rc5.
However, the proposal has several drawbacks.
It uses a separate stack for avoiding the Flip operation. This stack has a fixed size and thereby
is too large in most cases and too small in the extreme case of very deeply nested data structures.
The stack is also hard to understand but in principle it works.

Note that there is no need for such a stack because of the recursive
structure of the dump procedures. The stack can be maintained easily
inside the recursive dump procedures which is simpler to read and avoids a fixed
size auxiliary stack.

For the changes based on the pproposal in CPC 1.7 rc5 but without an explicit stack see http://redmine.blackboxframework.org/pr ... 3cd5beae40.

- Josef
User avatar
DGDanforth
Posts: 1061
Joined: Tue Sep 17, 2013 1:16 am
Location: Palo Alto, California, USA
Contact:

Re: issue-#72 speeding up the dump of large data structures

Post by DGDanforth »

I notice the string

Code: Select all

"   "
occurs 16 times (8 times in each module). I would think a better approach
following the rule "one place only" would be to define,

Code: Select all

CONST spacer = "   "
and use

Code: Select all

spacer
for those occurrences.

-Doug
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#72 speeding up the dump of large data structures

Post by Josef Templ »

> I notice the string " " occurs 16 times (8 times in each module).

Certainly true, but not related to THIS issue.
It can be changed in an attempt of beautifying the sources such as in
CPC 1.7 rc5 change list number 22 (changes by Trurl), which contain
lots of similar beautifications.

- Josef
Zinn
Posts: 476
Joined: Tue Mar 25, 2014 5:56 pm
Location: Frankfurt am Main
Contact:

Re: issue-#72 speeding up the dump of large data structures

Post by Zinn »

Josef, your solution is perfect and better as the one in CPC.
I think, it is ready for voting on it.
- Helmut
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#72 speeding up the dump of large data structures

Post by Josef Templ »

Thanks, Helmut. Just go ahead with the voting.
Ivan Denisov
Posts: 1700
Joined: Tue Sep 17, 2013 12:21 am
Location: Russia

Re: issue-#72 speeding up the dump of large data structures

Post by Ivan Denisov »

I found the description in Russian and now I am understanding the problem better!
http://forum.oberoncore.ru/viewtopic.ph ... 740#p75740

Ilya gave there the example of test code.

Code: Select all

MODULE TestDo;
	IMPORT  Log, Math;
	PROCEDURE Test*;
	VAR dat: ARRAY 4096 OF ARRAY 2 OF ARRAY 2 OF INTEGER;
	BEGIN
	HALT(0)
	END Test;
END TestDo.Test
So I compared the time before and after this fix. I used version:
http://blackboxframework.org/unstable/i ... a1.239.zip
With fix it takes only 3-4 seconds to build the TRAP window, without fix it takes 30-40 sec!

I was abstaining from voting, because did not understand the issue well. Now all is clear and I am changing my voice from Abstain to Yes.
Post Reply