dateibeziehungen.pas: tMach.findeWasZuTunIst: Redundanzenentfernen beschleunigt

3 files changed, 200 insertions, 105 deletions

diff --git a/Make.lpr b/Make.lpr
index e7b862e..e23f501 100644
--- a/Make.lpr
+++ b/Make.lpr
@@ -1,5 +1,7 @@
 program Make;
 
+{$DEFINE UseCThreads}
+
 {$mode objfpc}{$H+}
 
 uses
diff --git a/Make.lps b/Make.lps
index 6f89b0f..c3a62a2 100644
--- a/Make.lps
+++ b/Make.lps
@@ -3,29 +3,28 @@
   <ProjectSession>
     <Version Value="10"/>
     <BuildModes Active="Default"/>
-    <Units Count="18">
+    <Units Count="19">
       <Unit0>
         <Filename Value="Make.lpr"/>
         <IsPartOfProject Value="True"/>
-        <TopLine Value="46"/>
-        <CursorPos Y="68"/>
-        <UsageCount Value="120"/>
+        <CursorPos Y="3"/>
+        <UsageCount Value="125"/>
         <Loaded Value="True"/>
       </Unit0>
       <Unit1>
         <Filename Value="Machdatei.txt"/>
         <IsPartOfProject Value="True"/>
-        <UsageCount Value="120"/>
+        <UsageCount Value="125"/>
         <DefaultSyntaxHighlighter Value="None"/>
       </Unit1>
       <Unit2>
         <Filename Value="tools.pas"/>
         <IsPartOfProject Value="True"/>
         <EditorIndex Value="5"/>
-        <TopLine Value="200"/>
-        <CursorPos Y="254"/>
-        <FoldState Value=" T3ie059 piejO057 pj5jQ0M]9lLmI0D5]I6jV032O"/>
-        <UsageCount Value="99"/>
+        <TopLine Value="96"/>
+        <CursorPos X="24" Y="185"/>
+        <FoldState Value=" T3j0059 piejO057]9fjJ0Q[94Zja0{u6 pjJmf032!"/>
+        <UsageCount Value="104"/>
         <Loaded Value="True"/>
       </Unit2>
       <Unit3>
@@ -34,7 +33,7 @@
         <EditorIndex Value="3"/>
         <TopLine Value="459"/>
         <CursorPos X="36" Y="377"/>
-        <UsageCount Value="96"/>
+        <UsageCount Value="101"/>
         <Loaded Value="True"/>
       </Unit3>
       <Unit4>
@@ -43,29 +42,30 @@
         <UnitName Value="dateiBeziehungen"/>
         <IsVisibleTab Value="True"/>
         <EditorIndex Value="1"/>
-        <CursorPos X="38" Y="7"/>
-        <FoldState Value=" T3jc03C pjYkO0B4 pk5kQ0l312 piXmO066]T4jQ0F1[K5fld0G2[K733u"/>
-        <UsageCount Value="88"/>
+        <TopLine Value="1036"/>
+        <CursorPos X="12" Y="1064"/>
+        <FoldState Value=" T3k803B15 pkGo70l312 piXmO066]9bjG0F1[K5fld0G01]Mj7lS0OP"/>
+        <UsageCount Value="93"/>
         <Loaded Value="True"/>
       </Unit4>
       <Unit5>
         <Filename Value="Machdatei"/>
         <CursorPos X="45" Y="17"/>
-        <UsageCount Value="6"/>
+        <UsageCount Value="5"/>
         <DefaultSyntaxHighlighter Value="None"/>
       </Unit5>
       <Unit6>
         <Filename Value="../Stabile/lowlevelunit.pas"/>
         <EditorIndex Value="-1"/>
         <CursorPos X="26" Y="23"/>
-        <UsageCount Value="5"/>
+        <UsageCount Value="4"/>
       </Unit6>
       <Unit7>
         <Filename Value="../units/lowlevelunit.pas"/>
         <EditorIndex Value="4"/>
-        <TopLine Value="121"/>
-        <CursorPos Y="154"/>
-        <UsageCount Value="27"/>
+        <TopLine Value="1306"/>
+        <CursorPos X="47" Y="1321"/>
+        <UsageCount Value="30"/>
         <Loaded Value="True"/>
       </Unit7>
       <Unit8>
@@ -73,40 +73,40 @@
         <EditorIndex Value="-1"/>
         <TopLine Value="140"/>
         <CursorPos X="10" Y="160"/>
-        <UsageCount Value="6"/>
+        <UsageCount Value="5"/>
       </Unit8>
       <Unit9>
         <Filename Value="/usr/lib/fpc/src/rtl/objpas/math.pp"/>
         <EditorIndex Value="-1"/>
         <TopLine Value="162"/>
         <CursorPos X="10" Y="167"/>
-        <UsageCount Value="6"/>
+        <UsageCount Value="5"/>
       </Unit9>
       <Unit10>
         <Filename Value="../units/matheunit.pas"/>
         <EditorIndex Value="-1"/>
-        <UsageCount Value="6"/>
+        <UsageCount Value="5"/>
       </Unit10>
       <Unit11>
         <Filename Value="/usr/lib/fpc/src/rtl/objpas/sysutils/finah.inc"/>
         <EditorIndex Value="-1"/>
         <TopLine Value="4"/>
         <CursorPos X="10" Y="23"/>
-        <UsageCount Value="6"/>
+        <UsageCount Value="5"/>
       </Unit11>
       <Unit12>
         <Filename Value="/usr/lib/fpc/src/rtl/objpas/classes/classesh.inc"/>
         <EditorIndex Value="-1"/>
         <TopLine Value="1983"/>
         <CursorPos X="21" Y="1992"/>
-        <UsageCount Value="10"/>
+        <UsageCount Value="9"/>
       </Unit12>
       <Unit13>
         <Filename Value="../units/systemunit.pas"/>
         <EditorIndex Value="2"/>
         <TopLine Value="188"/>
-        <CursorPos X="17" Y="204"/>
-        <UsageCount Value="21"/>
+        <CursorPos X="16" Y="204"/>
+        <UsageCount Value="24"/>
         <Loaded Value="True"/>
       </Unit13>
       <Unit14>
@@ -115,20 +115,20 @@
         <EditorIndex Value="-1"/>
         <TopLine Value="56"/>
         <CursorPos X="14" Y="72"/>
-        <UsageCount Value="10"/>
+        <UsageCount Value="9"/>
       </Unit14>
       <Unit15>
         <Filename Value="/usr/lib/fpc/src/rtl/inc/objpash.inc"/>
         <EditorIndex Value="-1"/>
         <TopLine Value="402"/>
         <CursorPos X="31" Y="421"/>
-        <UsageCount Value="10"/>
+        <UsageCount Value="9"/>
       </Unit15>
       <Unit16>
         <Filename Value="Make.1.in"/>
         <EditorIndex Value="-1"/>
         <TopLine Value="42"/>
-        <UsageCount Value="9"/>
+        <UsageCount Value="8"/>
         <DefaultSyntaxHighlighter Value="None"/>
       </Unit16>
       <Unit17>
@@ -136,127 +136,136 @@
         <EditorIndex Value="-1"/>
         <TopLine Value="7"/>
         <CursorPos X="10" Y="25"/>
-        <UsageCount Value="10"/>
+        <UsageCount Value="9"/>
       </Unit17>
+      <Unit18>
+        <Filename Value="/usr/lib/fpc/src/rtl/linux/sysosh.inc"/>
+        <EditorIndex Value="-1"/>
+        <TopLine Value="4"/>
+        <CursorPos X="3" Y="28"/>
+        <UsageCount Value="10"/>
+      </Unit18>
     </Units>
     <JumpHistory Count="30" HistoryIndex="29">
       <Position1>
-        <Filename Value="tools.pas"/>
-        <Caret Line="29" Column="13"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1023" TopLine="1020"/>
       </Position1>
       <Position2>
-        <Filename Value="tools.pas"/>
-        <Caret Line="96" Column="21" TopLine="67"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1028" TopLine="996"/>
       </Position2>
       <Position3>
-        <Filename Value="tools.pas"/>
-        <Caret Line="102" Column="21" TopLine="73"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1034" TopLine="1017"/>
       </Position3>
       <Position4>
-        <Filename Value="tools.pas"/>
-        <Caret Line="112" Column="21" TopLine="83"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1042" Column="25" TopLine="1025"/>
       </Position4>
       <Position5>
-        <Filename Value="tools.pas"/>
-        <Caret Line="113" Column="30" TopLine="84"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="133" Column="19" TopLine="113"/>
       </Position5>
       <Position6>
-        <Filename Value="tools.pas"/>
-        <Caret Line="114" Column="13" TopLine="85"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1042" Column="87" TopLine="1032"/>
       </Position6>
       <Position7>
-        <Filename Value="tools.pas"/>
-        <Caret Line="128" Column="47" TopLine="117"/>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <Caret Line="154" TopLine="121"/>
       </Position7>
       <Position8>
-        <Filename Value="tools.pas"/>
-        <Caret Line="134" Column="24" TopLine="117"/>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <Caret Line="1319" Column="41" TopLine="1301"/>
       </Position8>
       <Position9>
-        <Filename Value="tools.pas"/>
-        <Caret Line="138" Column="69" TopLine="117"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1023" Column="48" TopLine="909"/>
       </Position9>
       <Position10>
-        <Filename Value="tools.pas"/>
-        <Caret Line="137" Column="55" TopLine="117"/>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <Caret Line="156" Column="44" TopLine="145"/>
       </Position10>
       <Position11>
-        <Filename Value="tools.pas"/>
-        <Caret Line="138" Column="69" TopLine="117"/>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <Caret Line="23" Column="55"/>
       </Position11>
       <Position12>
-        <Filename Value="tools.pas"/>
-        <Caret Line="140" Column="55" TopLine="117"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1062" Column="153" TopLine="1044"/>
       </Position12>
       <Position13>
-        <Filename Value="tools.pas"/>
-        <Caret Line="143" Column="20" TopLine="117"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="116" Column="28" TopLine="106"/>
       </Position13>
       <Position14>
-        <Filename Value="tools.pas"/>
-        <Caret Line="144" Column="28" TopLine="117"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1021" Column="64" TopLine="693"/>
       </Position14>
       <Position15>
-        <Filename Value="tools.pas"/>
-        <Caret Line="145" Column="15" TopLine="117"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1063" Column="60" TopLine="1035"/>
       </Position15>
       <Position16>
-        <Filename Value="tools.pas"/>
-        <Caret Line="170" Column="25" TopLine="133"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1161" Column="16" TopLine="1074"/>
       </Position16>
       <Position17>
-        <Filename Value="tools.pas"/>
-        <Caret Line="178" Column="84" TopLine="141"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="105" TopLine="104"/>
       </Position17>
       <Position18>
-        <Filename Value="tools.pas"/>
-        <Caret Line="190" Column="21" TopLine="153"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1162" Column="14" TopLine="1143"/>
       </Position18>
       <Position19>
-        <Filename Value="tools.pas"/>
-        <Caret Line="230" Column="29" TopLine="177"/>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <Caret Line="24" Column="44" TopLine="13"/>
       </Position19>
       <Position20>
-        <Filename Value="tools.pas"/>
-        <Caret Line="232" Column="26" TopLine="179"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1155" Column="170" TopLine="1143"/>
       </Position20>
       <Position21>
-        <Filename Value="tools.pas"/>
-        <Caret Line="268" Column="39" TopLine="227"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="125" Column="148" TopLine="107"/>
       </Position21>
       <Position22>
-        <Filename Value="tools.pas"/>
-        <Caret Line="269" Column="27" TopLine="228"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1055" Column="66" TopLine="1033"/>
       </Position22>
       <Position23>
-        <Filename Value="tools.pas"/>
-        <Caret Line="270" Column="28" TopLine="229"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1168" Column="3" TopLine="1148"/>
       </Position23>
       <Position24>
-        <Filename Value="tools.pas"/>
-        <Caret Line="271" Column="13" TopLine="230"/>
+        <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="120" Column="118" TopLine="103"/>
       </Position24>
       <Position25>
         <Filename Value="dateibeziehungen.pas"/>
-        <Caret Line="499" TopLine="311"/>
+        <Caret Line="1020" Column="30" TopLine="804"/>
       </Position25>
       <Position26>
         <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1048" Column="24" TopLine="1031"/>
       </Position26>
       <Position27>
         <Filename Value="dateibeziehungen.pas"/>
-        <Caret Line="546" Column="9" TopLine="518"/>
+        <Caret Line="1051" Column="52" TopLine="1031"/>
       </Position27>
       <Position28>
-        <Filename Value="dateibeziehungen.pas"/>
-        <Caret Line="499" TopLine="70"/>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <Caret Line="157" Column="10" TopLine="140"/>
       </Position28>
       <Position29>
         <Filename Value="dateibeziehungen.pas"/>
+        <Caret Line="1073" Column="46" TopLine="1054"/>
       </Position29>
       <Position30>
         <Filename Value="dateibeziehungen.pas"/>
-        <Caret Line="1151" TopLine="700"/>
+        <Caret Line="1172" TopLine="751"/>
       </Position30>
     </JumpHistory>
   </ProjectSession>
diff --git a/dateibeziehungen.pas b/dateibeziehungen.pas
index 902f724..c0d258e 100644
--- a/dateibeziehungen.pas
+++ b/dateibeziehungen.pas
@@ -5,7 +5,7 @@ unit dateiBeziehungen;
 interface
 
 uses
-  classes, sysUtils, tools, regExpr, mystringlistunit;
+  classes, sysUtils, tools, regExpr, mystringlistunit, lowlevelunit;
 
 type
   tZeilenTyp = (ztSuche,ztZiel,ztQuelle,ztBefehl);
@@ -113,12 +113,25 @@ type
     function anzDats: longint; inline;
   end;
 
+  tRedundanzenEntfernThread = class(tThread)
+  private
+    num,anz:  longint;
+    mglAbh:   tExpliziteAbhaengigkeiten;
+    ztd,itpf: pTLongintArray;      // die inversToepfe müssen nur auf _einen_ Topf je mglAbh zeigen, nicht auf alle.
+    tpf:      pTLongintArrayArray;
+    kA:       pRTLCriticalSection;
+    fertig:   boolean;
+  public
+    constructor create(nummer,anzahl: longint; moeglicheAbhaengigkeiten: tExpliziteAbhaengigkeiten; zuTunDurch,inversToepfe: pTLongintArray; toepfe: pTLongintArrayArray; kritischerAbschnitt: pRTLCriticalSection);
+    procedure execute; override;
+  end;
+
 procedure allgemeineErsetzungen(var worin: string; worinIstRegex: tRegexTyp; machDatei: string);
 
 implementation
 
 uses
-  lowlevelunit, systemunit;
+  systemunit, math;
 
 // tGenerischeAbhaengigkeiten ************************************************************
 
@@ -1002,41 +1015,72 @@ end;
 
 procedure tMach.findeWasZuTunIst;
 var
-  i,j:   longint;
-  neues: boolean;
-  zuTun: array of boolean;
+  i,j:                       longint;
+  neues:                     boolean;
+  zuTunDurch,inversToepfe:   tLongintArray;
+  redundanzenEntfernThreads: array of tRedundanzenEntfernThread;
+  kritischerAbschnitt:       tRTLCriticalSection;
+  fertig:                    boolean;
+  toepfe:                    tLongintArrayArray;
 begin
-  setLength(zuTun,_mglAbh.count);
-  for i:=0 to length(zuTun)-1 do
-    zuTun[i]:=false;
+  setLength(zuTunDurch,_mglAbh.count);
+  for i:=0 to length(zuTunDurch)-1 do
+    zuTunDurch[i]:=-1;
 
+  j:=0;
   // schauen, welche Regeln angewandt werden müssen
   repeat
     neues:=false;
-    for i:=0 to length(zuTun)-1 do
-      if not zuTun[i] then
+    for i:=0 to length(zuTunDurch)-1 do
+      if zuTunDurch[i]=-1 then
         if _mglAbh[i].pruefeObZuTun then begin
-          zuTun[i]:=true;
+          inc(j);
+          zuTunDurch[i]:=i;
           neues:=true;
         end;
   until not neues;
 
-  // schauen, welche Regeln redundant sind
-  for i:=0 to length(zuTun)-1 do
-    if zuTun[i] then
-      for j:=0 to length(zuTun)-1 do
-        if zuTun[j] and (i<>j) and _mglAbh[i].ersetzbarDurch(_mglAbh[j]) then begin
-          _mglAbh[j].quellen.append(_mglAbh[i].quellen);
-          zuTun[i]:=false;
-          break;
-        end;
+  setLength(toepfe,max(1,round(sqrt(j)))); // wir verteilen die _mglAbh je nach ihren Zielen auf toepfe
+  for i:=0 to length(toepfe)-1 do
+    setLength(toepfe[i],0);
+  setLength(inversToepfe,length(zuTunDurch));
+  for i:=0 to length(inversToepfe)-1 do
+    inversToepfe[i]:=-1;
+  for i:=0 to length(zuTunDurch)-1 do
+    if zuTunDurch[i]>=0 then
+      for j:=0 to _mglAbh[i].ziele.count-1 do begin
+        inversToepfe[i]:=pruefSumme(_mglAbh[i].ziele[j].name,length(toepfe)); // wir merken uns nur den Topf des letzten Zieles - (mindestens) in diesem Topf muss auch die Obermenge liegen
+        setLength(toepfe[inversToepfe[i]],length(toepfe[inversToepfe[i]])+1);
+        toepfe[inversToepfe[i]][length(toepfe[inversToepfe[i]])-1]:=i;
+      end;
 
-  for i:=length(zuTun)-1 downto 0 do
-    if not zuTun[i] then begin
+  for i:=0 to length(zuTunDurch)-1 do begin
+    assert(_mglAbh[i].ziele.count>0,'Hier ist eine Abhängigkeit ohne Ziele!');
+    _mglAbh[i].ziele.sItems[0]; // sortieren!
+  end;
+
+  // schauen, welche Regeln redundant sind
+  initCriticalSection(kritischerAbschnitt);
+  setLength(redundanzenEntfernThreads,numCpus);
+  for i:=0 to length(redundanzenEntfernThreads)-1 do
+    redundanzenEntfernThreads[i]:=tRedundanzenEntfernThread.create(i,length(redundanzenEntfernThreads),_mglAbh,@zuTunDurch,@inversToepfe,@toepfe,@kritischerAbschnitt);
+  repeat
+    fertig:=true;
+    for i:=0 to length(redundanzenEntfernThreads)-1 do
+      fertig:=redundanzenEntfernThreads[i].fertig and fertig;
+    if not fertig then
+      sleep(10);
+  until fertig;
+  for i:=0 to length(redundanzenEntfernThreads)-1 do
+    redundanzenEntfernThreads[i].free;
+  doneCriticalsection(kritischerAbschnitt);
+
+  for i:=length(zuTunDurch)-1 downto 0 do
+    if zuTunDurch[i]<>i then begin
       _mglAbh[i].free;
       _mglAbh.delete(i);
     end;
-  setLength(zuTun,0);
+  setLength(zuTunDurch,0);
 
   // anzuwendende Regeln sortieren
   _mglAbh.sort;
@@ -1109,6 +1153,46 @@ begin
   result:=_dats.count;
 end;
 
+// tRedundanzenEntfernThread ***************************************************
+
+constructor tRedundanzenEntfernThread.create(nummer,anzahl: longint; moeglicheAbhaengigkeiten: tExpliziteAbhaengigkeiten; zuTunDurch,inversToepfe: pTLongintArray; toepfe: pTLongintArrayArray; kritischerAbschnitt: pRTLCriticalSection);
+begin
+  inherited create(true);
+  num:=nummer;
+  anz:=anzahl;
+  mglAbh:=moeglicheAbhaengigkeiten;
+  ztd:=zuTunDurch;
+  tpf:=toepfe;
+  itpf:=inversToepfe;
+  kA:=kritischerAbschnitt;
+  fertig:=false;
+  suspended:=false;
+end;
+
+procedure tRedundanzenEntfernThread.execute;
+var
+  i,j: longint;
+begin
+  i:=num;
+  while i<=length(ztd^)-1 do begin
+    if ztd^[i]=i then begin
+      assert(mglAbh[i].ziele.istSortiert,'tRedundanzenEntfernThread.execute: mglAbh['+intToStr(i)+'].ziele sind nicht sortiert - das kann ich im Thread aber nicht machen!');
+      for j:=0 to length(tpf^[itpf^[i]])-1 do begin
+        assert(mglAbh[tpf^[itpf^[i],j]].ziele.istSortiert,'tRedundanzenEntfernThread.execute: mglAbh['+intToStr(tpf^[itpf^[i],j])+'].ziele sind nicht sortiert - das kann ich im Thread aber nicht machen!');
+        if (ztd^[tpf^[itpf^[i],j]]>=0) and (i<>tpf^[itpf^[i],j]) and mglAbh[i].ersetzbarDurch(mglAbh[tpf^[itpf^[i],j]]) then begin // ersetzbarDurch ist transitiv!
+          enterCriticalsection(kA^);
+          mglAbh[ztd^[tpf^[itpf^[i],j]]].quellen.append(mglAbh[i].quellen);
+          ztd^[i]:=ztd^[tpf^[itpf^[i],j]];
+          leaveCriticalsection(kA^);
+          break;
+        end;
+      end;
+    end;
+    i:=i+anz;
+  end;
+  fertig:=true;
+end;
+
 // allgemeine Funktionen
 
 procedure allgemeineErsetzungen(var worin: string; worinIstRegex: tRegexTyp; machDatei: string);