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
issue-#72 speeding up the dump of large data structures
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
- 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
I notice the string occurs 16 times (8 times in each module). I would think a better approach
following the rule "one place only" would be to define,
and use for those occurrences.
-Doug
Code: Select all
" "
following the rule "one place only" would be to define,
Code: Select all
CONST spacer = " "
Code: Select all
spacer
-Doug
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#72 speeding up the dump of large data structures
> 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
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
Re: issue-#72 speeding up the dump of large data structures
Josef, your solution is perfect and better as the one in CPC.
I think, it is ready for voting on it.
- Helmut
I think, it is ready for voting on it.
- Helmut
- Josef Templ
- Posts: 2047
- Joined: Tue Sep 17, 2013 6:50 am
Re: issue-#72 speeding up the dump of large data structures
Thanks, Helmut. Just go ahead with the voting.
-
- Posts: 1700
- Joined: Tue Sep 17, 2013 12:21 am
- Location: Russia
Re: issue-#72 speeding up the dump of large data structures
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.
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.
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
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.