I don't think static constructors are required in .di files. Without that bit of info, I don't think the cycle detection can be done until runtime.
I still hope that a cycle detection algorithm can be used that's quicker than O(n^3), hopefully something like O(n^2) as the current flawed algorithm is. -Steve ----- Original Message ---- > From: Sean Kelly <[email protected]> > To: Discuss the phobos library for D <[email protected]> > Sent: Tue, June 22, 2010 1:40:02 PM > Subject: Re: [phobos] Proposed feature: print cycle when a module cyclic > dependency is detected > > Yeah, it makes sense to have the cycle detection only run on startup. It > should probably be extracted from _moduleCtor2() and _moduleTlsCtor() and > just > run as a unit before the ctors are called on program startup. It would be > even better if cycle detection could be done by the compiler at build time, > but > perhaps this is an instance where build speed should be favored over startup > speed. On Jun 22, 2010, at 9:24 AM, Steve Schveighoffer > wrote: > Hm... this is turning out to be quite an interesting > problem. > > I'm thinking a full cycle detection algorithm might be > required, like Floyd-Warshall, but that's O(n^3), so it would be painful to > run > on the start of every thread. 100 modules == 1,000,000 iterations. > > > The thing about it is, once the order of executing the static > constructors is decided, it will never change. So potentially, we can > determine order of static constructor/destructor execution at the beginning > of > the runtime startup, and then simply run through the order when > creating/destroying a thread. > > I'm not exactly convinced that we > can't find some quicker way, but so far, I'm not finding it. The problem > is for "forwarding modules", or modules that contain no constructors, but > have > dependencies on other modules that do. The example I gave is probably a > minimal example of the problem. The current runtime short-circuits itself > by not running any dependencies of such modules more than once. But this > leads to not detecting cycles where the forwarding modules are used more than > once. > > Whatever the cycle detection algorithm, I'm *absolutely* > convinced the running of the constructors/destructors themselves should be > separate from the cycle detection. We shouldn't be detecting cycles on > every thread start in an unchanging graph. > > -Steve > > > > > > ----- Original Message ---- >> > From: Steve Schveighoffer < > href="mailto:[email protected]";>[email protected]> >> To: > Discuss the phobos library for D < > href="mailto:[email protected]";>[email protected]> >> > Sent: Tue, June 22, 2010 9:57:41 AM >> Subject: Re: [phobos] Proposed > feature: print cycle when a module cyclic dependency is detected >> > >> OK, I found a bug in the cycle detection. > > For some > reason, the module >> cycle detection has a weird rule where if a > module has no static ctors/dtors, it >> skips cycle detection on its > immediate dependencies. Here is a test case >> where the cycle > detection fails, and the results: > > mod1.d: > > > public >> import mod2; > public import mod3; > private > import std.stdio; > > void >> main() > > { > writefln("x = %d, y = %d", x, >> y); > > } > > mod2.d: > import mod1; > > __gshared int > x; > > static >> this() > { > > version(xfirst) > x = 1; > >> > else > x = y; > } > > > mod3.d: > import >> mod1; > > __gshared int > y; > > static this() > { > >> > version(xfirst) > y = x; > else > > >> y = 1; > } > > the results: > > [ste...@steveslaptop testmodules]$ dmd >> -version=xfirst mod1.d > mod2.d mod3.d -ofxfirst > [ste...@steveslaptop >> testmodules]$ > dmd mod1.d mod2.d mod3.d -ofyfirst > [ste...@steveslaptop >> > testmodules]$ ./xfirst > x = 1, y = 1 > [ste...@steveslaptop > testmodules]$ >> ./yfirst > x = 0, y = 1 > > And > yes, I did apply Don's fix to the module >> constructor. What > I'm trying to understand is the logic behind the "skip" >> flag that > implements this "feature". There seems to be no explanation for > >> it. > > Also, while I have your attention on this, > what triggers the compiler >> to set the MIstandalone flag? > > > I don't mind fixing these problems, but I >> want to > understand the logic behind it first. > > -Steve > > > > > ----- >> Original Message ---- >> From: > Steve Schveighoffer < >> ymailto="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]" >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> >> To: > >> Discuss the phobos library for D < >> href="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> >> > Sent: >> Tue, June 22, 2010 9:24:54 AM >> Subject: Re: > [phobos] Proposed feature: >> print cycle when a module cyclic > dependency is detected >> >> I just >> realized > that this patch isn't good enough (it does not print modules >> > >> which have no constructors/destructors but which import other > modules), I'm >> >> working on a better one. > > > But it's definitely possible. So >> assume I > >> will have a patch shortly, does the concept seem >> > >> worthy? > > -Steve > > > > > ----- Original Message ---- >> From: >> >> Steve > Schveighoffer < >> href="mailto: >> ymailto="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]" >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> >> > ymailto="mailto: > href="mailto:[email protected]";>[email protected]" >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> >> To: > Phobos >> >> < >> href="mailto: >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> >> > ymailto="mailto: > href="mailto:[email protected]";>[email protected]" >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> >> > Sent: >> >> Tue, June 22, 2010 8:59:23 AM >> > Subject: [phobos] Proposed >> feature: print >> cycle when a > module cyclic dependency is >> detected >> >> Hi > >> all, > > Recently, I had an issue when >> > developing std.process. I >> >> inadvertently caused a > cyclic >> dependency in modules. However, the >> error > >> was not enough >> to find the problem: > > > object.Exception: >> Cyclic dependency >> >> in > module std.stdio > > The problem is, this is >> the *end* > >> of the cycle, not >> the source. I actually hadn't > changed >> >> the imports of std.stdio. > > So > >> I improved the module constructor >> >> > function to automatically print all modules >> involved in the > >> cycle, in >> the order they were imported. Attached > is the >> >> patch. The >> function should > not adversely affect the runtime in >> normal >> operation, > >> since the changes I made only occur when a >> terminating > exception is >> >> about to be thrown anyways. Do > >> people agree this is a worthy improvement >> >> > to the >> runtime? Anyone see any issues with the patch? If > everyone >> likes, >> >> I'll commit. > > > -Steve > > > >> >> > > _______________________________________________ > phobos mailing > >> list > >> ymailto="mailto: >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]" >> > >> href="mailto: >> href="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> >> > ymailto="mailto: > href="mailto:[email protected]";>[email protected]" >> > href="mailto: > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > > http://lists.puremagic.com/mailman/listinfo/phobos > > > > >> > _______________________________________________ > > phobos >> mailing list > >> href="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] > >> > href=" > >http://lists.puremagic.com/mailman/listinfo/phobos"; target=_blank > >>> > target=_blank >http://lists.puremagic.com/mailman/listinfo/phobos > > > > > > _______________________________________________ > phobos mailing > list > > href="mailto:[email protected]";>[email protected] > > href="http://lists.puremagic.com/mailman/listinfo/phobos"; target=_blank > >http://lists.puremagic.com/mailman/listinfo/phobos _______________________________________________ phobos > mailing list > href="mailto:[email protected]";>[email protected] > href="http://lists.puremagic.com/mailman/listinfo/phobos"; target=_blank > >http://lists.puremagic.com/mailman/listinfo/phobos _______________________________________________ phobos mailing list [email protected] http://lists.puremagic.com/mailman/listinfo/phobos
