[NTG-context] Variable instance identifiers exhausted

Hans Hagen j.hagen at xs4all.nl
Fri Sep 21 19:28:52 CEST 2018


On 9/21/2018 5:04 PM, Fabrice L wrote:
> Le 19 septembre 2018 à 15:47:07, Fabrice L (fabrice.alpha at gmail.com 
> <mailto:fabrice.alpha at gmail.com>) a écrit:
>>
>>
>>
>> Le 19 septembre 2018 à 15:28:54, Alan Braslau 
>> (braslau.list at comcast.net 
>> <mailto:braslau.list at comcast.net>(mailto:braslau.list at comcast.net 
>> <mailto:braslau.list at comcast.net>)) a écrit:
>>
>> > On Tue, 18 Sep 2018 19:21:31 -0700   
>> > Fabrice L wrote:   
>> >   
>> > > The problem is that the process take hours of compilations, and   
>> > > tests are not easy to do. Anyway, I will enrich my « minimal » code to my   
>> > > « full » code in order to find the difference… and the problem. I will   
>> > > update the thread as soon as can.   
>> >   
>> > My over 700k object graphics example, processed several times (repeatedly, over several pages with modifications) took less than one minute to process. In fact, each graphic took almost as long to render from the pdf as it did for metapost/lua to process.   
>> > 
>> > Alan 
>>
>> I do not know what your example is (but I’m curious: can I see this 
>> somewhere ?).
>>
>> In my case, the long time needed is to check if a new object does not 
>> intersect with any other object: so when I try to find the maximum 
>> size of the 1000th object at a given position, I have to check with 
>> the 999 others… I do this with « intersectiontimes ». And so on for 
>> the 10001th… I have a course try to find solutions to gain time, like 
>> using the coordinate of a new object: when the coordinate of a new 
>> object is chosen, I do not need to check potential intersections with 
>> objects far away… but surprisingly (to me) this take more time than to 
>> blindly check with every object.
>>
>> This is an algorithmic problem more than a ConTeXt/Metapost one… but I 
>> you have suggestions, I’m sure I can learn !
>>
>> Below is minimal code. (Just to be clear, this code work, even for 20K 
>> objects.)
>> Thanks.
>>
>> \starttext
>>   \startMPpage
>>   path Obj[] , ObjTemp ;
>>   pair ObjPos , Inter ;
>>   numeric NObj ;
>>   % Change herte "NObj" to a big numer (says 20K)
>>   NObj := 100;
>>   numeric Danger, MaxSize ;
>>
>>   % Draw an initial object of random shape and random size ;
>>   Obj[1]:= fullsquare randomized .001in
>>   scaled (uniformdeviate(.5)*1in)
>>   shifted (uniformdeviate(5)*1in,uniformdeviate(5)*1in) ;
>>   Obj[1] := curved ( Obj[1] );
>>   fill Obj[1] withcolor cyan randomized (.2,1.5);
>>   draw Obj[1] withcolor black randomized (.2,1.5);
>>
>>   for i=2 upto NObj :
>>   Danger := 0;
>> % Choose a position for the object :
>>   ObjPos := (uniformdeviate(5)*1in,uniformdeviate(5)*1in) ;
>>   % Choose a form :
>>   Obj[i] := fullsquare randomized .01in ;
>>   Obj[i] := curved ( Obj[i] );
>>   % Choose a scale so the object does not interact with any other object:
>>     for j=1 upto 50:
>>        MaxSize := (j*.01in) ;
>>     ObjTemp := Obj[i] scaled MaxSize shifted ObjPos ;
>>        %draw ObjTemp withcolor magenta ;
>>        % Check if this temporary object intersect with any other object :
>>        for k=1 upto (i-1):
>>         string trace ;
>>          Inter := Obj[k] intersectiontimes ObjTemp ;
>>          if (xpart Inter) <> -1 : Danger := 1; fi ;
>>          if Danger=1: MaxSize := ((j-1)*.01in) ; fi;
>>          exitif Danger = 1;
>>        endfor;
>>        exitif Danger = 1;
>>   endfor ;
>>   Obj[i] := Obj[i] scaled MaxSize shifted ObjPos ;
>>
>>   fill Obj[i] withcolor cyan randomized (.2,1.5);
>>   draw Obj[i] withcolor black randomized (.2,1.5);
>>   endfor;
>>   \stopMPpage
>> \stoptext
>>
> 
> 
> So after some hours of computation, this code above breaks for me if the 
> number of objects,  NObj in my code, is too large. Of course, perhaps an 
> error occurs at some point and is not caused directly by the number of 
> objects, because according to what has been said in this thread this 
> should not be is not a problem. I put below the log. If somebody has a 
> hint in which direction I should look… thanks !
> 
> Fabrice.
> 
> mtx-context     | run 1: luatex 
> --fmt="/Users/fabricel/context/tex/texmf-cache/luatex-cache/context/5fe67e0bfe781ce0dde776fb1556f32e/formats/luatex/cont-en" 
> --jobname="0030-0018-minimal2" 
> --lua="/Users/fabricel/context/tex/texmf-cache/luatex-cache/context/5fe67e0bfe781ce0dde776fb1556f32e/formats/luatex/cont-en.lui" 
> --no-parse-first-line --c:currentrun=1 
> --c:fulljobname="./0030-0018-minimal2.tex" 
> --c:input="./0030-0018-minimal2.tex" --c:kindofrun=1 --c:maxnofruns=1 
> --c:runs="1" "cont-yes.mkiv"
> 
> This is LuaTeX, Version 1.08.0 (TeX Live 2018)
>   system commands enabled.
> open source     > level 1, order 1, name 
> '/Users/fabricel/context/tex/texmf-context/tex/context/base/mkiv/cont-yes.mkiv'
> system          >
> system          > ConTeXt  ver: 2018.05.17 18:32 MKIV beta  fmt: 
> 2018.5.18  int: english/english
> system          >
> system          > 'cont-new.mkiv' loaded
> open source     > level 2, order 2, name 
> '/Users/fabricel/context/tex/texmf-context/tex/context/base/mkiv/cont-new.mkiv'
> system          > beware: some patches loaded from cont-new.mkiv
> close source    > level 2, order 2, name 
> '/Users/fabricel/context/tex/texmf-context/tex/context/base/mkiv/cont-new.mkiv'
> system          > files > jobname '0030-0018-minimal2', input 
> './0030-0018-minimal2', result '0030-0018-minimal2'
> fonts           > latin modern fonts are not preloaded
> languages       > language 'en' is active
> open source     > level 2, order 3, name 
> '/Users/fabricel/Dropbox/Divers/Création/P030-Remplissage/0030-0018-minimal2.tex'
> fonts           > preloading latin modern fonts (second stage)
> fonts           > 'fallback modern-designsize rm 12pt' is loaded
> metapost        > initializing instance 'metafun' using format 'metafun'
> metapost        > loading 'metafun' as 
> '/Users/fabricel/context/tex/texmf-context/metapost/context/base/mpiv/metafun.mpiv' 
> using method 'default'
> metapost        > initializing number mode 'scaled'
> 
> tex error       > mp error on line 45 in file 
> /Users/fabricel/Dropbox/Divers/Création/P030-Remplissage/0030-0018-minimal2.tex:
> 
> ! Emergency stop.
> <for(12315)> ...(EXPR0)]intersectiontimes.ObjTemp;
> if(xpart.Inter)<>-1:Danger...
> <for(1)> ...)-1)*0.01in);fi;exitif.Danger=1;endfor
> ;exitif.Danger=1; ENDFOR
> <for(22896)> ...er=1;endfor;exitif.Danger=1;endfor
> ;Obj[(EXPR0)]:=Obj[(EXPR0)...
> <*> ...withcolor black randomized (.2,1.5); endfor
> ; ;
> variable instance identifiers exhausted
> 
> 35              if Danger=1: MaxSize := ((j-1)*.01in) ; fi;
> 36              exitif Danger = 1;
> 37            endfor;
> 38            exitif Danger = 1;
> 39 endfor ;
> 40 Obj[i] := Obj[i] scaled MaxSize shifted ObjPos ;
> 41
> 42 fill Obj[i] withcolor cyan randomized (.2,1.5);
> 43 draw Obj[i] withcolor black randomized (.2,1.5);
> 44       endfor;
> 45 >>    \stopMPpage
> 46     \stoptext
> 47

The following runs ok on my machine (2500 sec for 20K). Of coure the 
more steps, the slower as there's a linear check involved. Here are some 
tips:

- use an intermediate path variable which saves a lookup
- precalculate constants that you use
- try to minimize calculations
- choose better step values (Delta is about .8 so why not use 1)
- (maybe no in and scale later, not tested)
- partition the pseudo array
- avoid redundant tests

For sure it can be made faster (you know what your goal is so that is a 
challenge for you).

\starttext

\startMPpage

     path foo[][][][] ;

     def fooslot(expr c) =
         foo[c div 1000][c div 100][c div 10][c]
     enddef ;

     path Obj, ObjTemp ;
     pair ObjPos , Inter ;
     numeric NObj, LastK, LastJ ;
     numeric MaxSize, Delta, Finch ;
     boolean Danger ;

     numeric unit ; unit := in ;

     % unit := 100 ; % faster

     NObj := 20000 ;
     Delta := unit/100 ;
     Finch := 5*unit ;

     Obj := fullsquare randomized (unit/1000)
         scaled (uniformdeviate(unit/2))
         shifted (uniformdeviate(Finch),uniformdeviate(Finch)) ;
     Obj := curved Obj ;

     fooslot(1) := Obj ;

     fill Obj withcolor cyan  randomized (.2,1.5) ;
     draw Obj withcolor black randomized (.2,1.5) ;

     for i=2 step 1 until NObj :
         message(i) ;
         Danger := false ;
         ObjPos := (uniformdeviate(Finch),uniformdeviate(Finch)) ;
         Obj    := fullsquare randomized Delta ;
         Obj    := curved Obj ;
         fooslot(i) := Obj ;
         LastK := i - 1 ;

       % MaxSize := 0 ;
         for j=1 step 1 until 50 :
             LastJ   := j - 1 ;
             MaxSize := j * Delta ;
           % MaxSize := MaxSize + Delta ;
             ObjTemp := Obj scaled MaxSize shifted ObjPos ;
             for k=1 step 1 until LastK :
                 Inter := fooslot(k) intersectiontimes ObjTemp ;
                 if (xpart Inter) <> -1 :
                     Danger := true;
                     MaxSize := LastJ * Delta ;
                   % MaxSize := MaxSize - Delta ;
                     exitif true ;
                 fi ;
             endfor ;
             exitif Danger ;
         endfor ;

         % hm, why not just use ObjTemp here

         Obj := Obj scaled MaxSize shifted ObjPos ;

         fooslot(i) := Obj ;

         fill Obj withcolor cyan  randomized (.2,1.5) ;
         draw Obj withcolor black randomized (.2,1.5) ;
   endfor;

\stopMPpage

\stoptext

It's a start ...

Hans

-----------------------------------------------------------------
                                           Hans Hagen | PRAGMA ADE
               Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
        tel: 038 477 53 69 | www.pragma-ade.nl | www.pragma-pod.nl
-----------------------------------------------------------------


More information about the ntg-context mailing list