From 2bfe76754a11679d0a3493e8ffc5bd87cc86daf1 Mon Sep 17 00:00:00 2001 From: Erich Eckner Date: Tue, 20 Feb 2018 13:24:29 +0100 Subject: dateibeziehungen.pas: tMach.findeWasZuTunIst: Redundanzenentfernen beschleunigt --- Make.lpr | 2 + Make.lps | 173 +++++++++++++++++++++++++++------------------------ dateibeziehungen.pas | 130 +++++++++++++++++++++++++++++++------- 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 @@ - + - - - + + - + - - - - + + + + @@ -34,7 +33,7 @@ - + @@ -43,29 +42,30 @@ - - - + + + + - + - + - - - + + + @@ -73,40 +73,40 @@ - + - + - + - + - + - - + + @@ -115,20 +115,20 @@ - + - + - + @@ -136,127 +136,136 @@ - + + + + + + + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - + + - + - - + + + - + 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); -- cgit v1.2.3-70-g09d2