Compile-time AAs
Don has recently said that adding dynamic arrays at compile-time looks easy.
I'd also like to have compile-time associative arrays. So you can fill them
inside a CT function (the compiler may try to do the same for AAs created
inside a static this(){}), and save some run time.
Even if such compile-time AAs have to be immutable at run-time they can be
useful anyway.
A smarter implementation of such CT AAs may even use a perfet hashing, to make
them quite fast.
Bye,
bearophile
Re: Template Metaprogramming Made Easy (Huh?)
language_fan wrote: > The members of the last group have studied computer science and > languages, in particular. They have found a pet academic language, > typically a pure one, but paradigms may differ. In fact this is the group > which uses something other than the hybrid object-oriented/procedural > model. They appreciate a strong, orthogonal core language that scales > cleanly. They are not scared of esoteric non-C-like syntax. They use > languages that are not ready to take a step to the "real world" during > the 70 next years. Of the three types, this comes closest to describing me. Yet, I am completely self-taught, and my preferred language is still C++. (I wouldn't call it my pet language. I loathe C++, I just haven't found a suitable replacement yet.) Stereotypes are dangerous. -- Rainer Deyke - rain...@eldwood.com
Re: Floating point rounding modes: we should restrict them slightly
Don wrote:
> Rainer Deyke wrote:
>> Don't forget that "uses floating point" is a transitive property. Any
>> pure function that calls a pure-but-unmemoisable function is itself
>> pure-but-unmemoisable.
>
> This is incorrect.
Then I must have misunderstood your proposal. Either you did a poor job
of explaining it, or I did a poor job of trying to understand it, or
it's not as simple as you make it out to be.
Since I'm not really interested in discussing the details of floating
point rounding modes and memoisation, I'll just leave it at that.
>> Is there any real need to treat floating point state differently from
>> other global state in regard to "pure"?
>
> Yes. Because it's all-pervasive.
It only affects floating point operations. Other pieces of global state
(e.g. the global locale) affect other operations. Once you make a
special case for floating point mode, it's easy to argue that the
special case should be extended to other pieces of global data. A
general solution generally beats special cases.
Or maybe I'm completely overthinking this.
> Unless you treat it specially, you
> cannot use floating point in any pure function. That creates a
> restriction which is so severe that 'pure' becomes useless. Something
> like the following template function could not be pure:
>
> T add(T a, T b) { return a + b; }
In the presence of structs and class executing arbitrary code in opPlus,
you can't make this pure anyway. Unless you force opPlus itself to be
pure, which is almost certainly too restrictive for the current
definition of pure.
--
Rainer Deyke - rain...@eldwood.com
Re: Non-moving generational GC [was: Template Metaprogramming Made Easy (Huh?)]
On Mon, 14 Sep 2009 18:53:51 -0400, Fawzi Mohamed wrote: On 2009-09-14 17:07:00 +0200, "Robert Jacques" said: On Mon, 14 Sep 2009 09:39:51 -0400, Leandro Lucarella wrote: Jeremie Pelletier, el 13 de septiembre a las 22:58 me escribiste: [snip] I understand your points for using a separate memory manager, and I agree with you that having less active allocations make for faster sweeps, no matter how little of them are scanned for pointers. However I just had an idea on how to implement generational collection on a non-moving GC which should solve your issues (and well, mines too) with the collector not being fast enough. I need to do some hacking on I saw a paper about that. The idea was to simply have some list of objects/pages in each generation and modify that lists instead of moving objects. I can't remember the name of the paper so I can't find it now :S The problem with generational collectors (in D) is that you need read/write barriers to track inter-generational pointers (to be able to use pointers to younger generations in the older ones as roots when scanning), which can make the whole deal a little unpractical for a language that doesn't want to impose performance penalty to thing you wont use (I don't see a way to instrument read/writes to pointers to the GC only). This is why RC was always rejected as an algorithm for the GC in D, I think. my custom GC first, but I believe it could give yet another performance boost. I'll add my memory manager to my list of code modules to make public :) As a counter-point, objective-c just introduced a thread-local GC. According to a blog post (http://www.sealiesoftware.com/blog/archive/2009/08/28/objc_explain_Thread-local_garbage_collection.html) apparently this has allowed pause times similar to the pause times of the previous generational GC. (Except that the former is doing a full collect, and the later still has work to do) On that note, it would probably be a good idea if core.gc.BlkAttr supported shared and immutable state flags, which could be used to support a thread-local GC. 1) to allocate large objects that have a guard object it is a good idea to pass through the GC because if memory is tight a gc collection is triggered thereby possibly freeing some extra memory 2) using gc malloc is not faster than malloc, especially with several threads the single lock of the basic gc makes itself felt. for how I use D (not realtime) the two things I would like to see from new gc are: 1) multiple pools (at least one per cpu, with thread id hash to assign threads to a given pool). This to avoid the need of a global gc lock in the gc malloc, and if possible use memory close to the cpu when a thread is pinned, not to have really thread local memory, if you really need local memory different from the stack then maybe a separate process should be used. This is especially well doable with 64 bits, with 32 memory usage/fragmentation could become an issue. 2) multiple thread doing the collection (a main thread distributing the work to other threads (one per cpu), that do the mark phase using atomic ops). other better gc, less latency (but not at the cost of too much computation), would be nice to have, but are not a priority for my usage. Fawzi For what it's worth, the whole point of thread-local GC is to do 1) and 2). For the purposes of clarity, thread-local GC refers to each thread having it's own GC for non-shared objects + a shared GC for shared objects. Each thread's GC may allocate and collect independently of each other (e.g. in parallel) without locking/atomics/etc.
Re: std.string phobos
pc wrote: [snip] This looks great, but for inclusion in Phobos I'd love to do two things about it: 1. Make it work with any ranges of characters, not only strings. 2. Make it lazy, i.e. output a range. Andrei
Re: Writing a language parser in D
Hi Nick, Thanks. The grammar is already spec'ed for LL ans so looking for the course of least resistance. I've used GOLD and spoken with its author, Devin Cook, in the past though. It's rather cool in a way. Still it's great to see GOLD coming to a screen in the D village. > If you can't find anything you like for LL and don't mind switching to LALR > instead, I've recently released Goldie ( > http://www.dsource.org/projects/goldie ) which works in conjunction with > GOLD Parser Builder ( http://www.devincook.com/goldparser/ ). If you're > familiar with GOLD, Goldie is a GOLD Engine for D. I do plan to add support > for LL eventually, but that's kind of a ways off for now.
Re: Writing a language parser in D
"Justin Johansson" wrote in message news:h8m6qs$300...@digitalmars.com... > Can D people please recommend suitable tools for generating a parser (in > D) for an LL(1) grammar. There's bound to be much better parser generator > tools available nowadays, since my last foray into this area 10+ years ago > with YACC. I've heard of tools like bison, SableCC etc but apart from the > names know nothing about them. > > (Note. This question is not about writing a parser for D. It is about > writing a parser in D for another language which has an LL(1) grammar). > > Thanks in advance for all help. > If you can't find anything you like for LL and don't mind switching to LALR instead, I've recently released Goldie ( http://www.dsource.org/projects/goldie ) which works in conjunction with GOLD Parser Builder ( http://www.devincook.com/goldparser/ ). If you're familiar with GOLD, Goldie is a GOLD Engine for D. I do plan to add support for LL eventually, but that's kind of a ways off for now.
Re: Template Metaprogramming Made Easy (Huh?)
language_fan wrote: In fact this is the group which uses something other than the hybrid object-oriented/procedural model. Damn straight! They use a hybrid OO/procedural/functional model. Like D. Or C#. "Oh, but Prolog," you may say. And I admit, I've seen it used a couple times by academics. But I've seen similar languages used at my job, and we're not by any means an algorithms shop. I'm actually aware of very few languages that break the mold. There are toy languages like Befunge; there are solver-oriented languages like Prolog and Zimpl; and there are a couple oddities like METAFONT. What languages have you seen that are so innovative and different in paradigm?
Re: Non-moving generational GC [was: Template Metaprogramming Made Easy (Huh?)]
On 2009-09-14 17:07:00 +0200, "Robert Jacques" said: On Mon, 14 Sep 2009 09:39:51 -0400, Leandro Lucarella wrote: Jeremie Pelletier, el 13 de septiembre a las 22:58 me escribiste: [snip] I understand your points for using a separate memory manager, and I agree with you that having less active allocations make for faster sweeps, no matter how little of them are scanned for pointers. However I just had an idea on how to implement generational collection on a non-moving GC which should solve your issues (and well, mines too) with the collector not being fast enough. I need to do some hacking on I saw a paper about that. The idea was to simply have some list of objects/pages in each generation and modify that lists instead of moving objects. I can't remember the name of the paper so I can't find it now :S The problem with generational collectors (in D) is that you need read/write barriers to track inter-generational pointers (to be able to use pointers to younger generations in the older ones as roots when scanning), which can make the whole deal a little unpractical for a language that doesn't want to impose performance penalty to thing you wont use (I don't see a way to instrument read/writes to pointers to the GC only). This is why RC was always rejected as an algorithm for the GC in D, I think. my custom GC first, but I believe it could give yet another performance boost. I'll add my memory manager to my list of code modules to make public :) As a counter-point, objective-c just introduced a thread-local GC. According to a blog post (http://www.sealiesoftware.com/blog/archive/2009/08/28/objc_explain_Thread-local_garbage_collection.html) apparently this has allowed pause times similar to the pause times of the previous generational GC. (Except that the former is doing a full collect, and the later still has work to do) On that note, it would probably be a good idea if core.gc.BlkAttr supported shared and immutable state flags, which could be used to support a thread-local GC. 1) to allocate large objects that have a guard object it is a good idea to pass through the GC because if memory is tight a gc collection is triggered thereby possibly freeing some extra memory 2) using gc malloc is not faster than malloc, especially with several threads the single lock of the basic gc makes itself felt. for how I use D (not realtime) the two things I would like to see from new gc are: 1) multiple pools (at least one per cpu, with thread id hash to assign threads to a given pool). This to avoid the need of a global gc lock in the gc malloc, and if possible use memory close to the cpu when a thread is pinned, not to have really thread local memory, if you really need local memory different from the stack then maybe a separate process should be used. This is especially well doable with 64 bits, with 32 memory usage/fragmentation could become an issue. 2) multiple thread doing the collection (a main thread distributing the work to other threads (one per cpu), that do the mark phase using atomic ops). other better gc, less latency (but not at the cost of too much computation), would be nice to have, but are not a priority for my usage. Fawzi
Re: Template Metaprogramming Made Easy (Huh?)
Lutger Wrote: > language_fan wrote: > > > Mon, 14 Sep 2009 07:33:59 -0400, bearophile thusly wrote: > > > >> But lot of people will judge D against more modern languages like C#, > >> Scala or Java) and not against C. > > > > Programmers often belong to three kinds of groups. First come the fans of > > traditionally weakly typed compiled languages (basic, c, c++). They have > > tried some "dynamic" or "academic" languages but did not like them. They > > fancy efficiency and close to metal feel. They think compilation to > > native code is the best way to produce programs, and think types should > > reflect the feature set of their cpu. They believe the syntax C uses was > > defined by their God. > > > > The second group started with interpreted languages built by amateurs > > (php, ruby, python, some game scripting language etc). They do not > > understand the meaning the types or compilation. They prefer writing > > short programs that usually seem to work. They hate formal specifications > > and proofs about program properties. They are usually writing simple web > > applications or some basic shareware utilies no one uses. They also hate > > trailing semicolons. > > > > The members of the last group have studied computer science and > > languages, in particular. They have found a pet academic language, > > typically a pure one, but paradigms may differ. In fact this is the group > > which uses something other than the hybrid object-oriented/procedural > > model. They appreciate a strong, orthogonal core language that scales > > cleanly. They are not scared of esoteric non-C-like syntax. They use > > languages that are not ready to take a step to the "real world" during > > the 70 next years. > > > > That's a fancy way of saying that anyone who has not studied CS is a moron > and therefore cannot understand what is good about languages, thus they lose > any argument automatically. Am I right? > I dunno if that's what OP meant, but studying CS does not make you a reference in programming languages. I didn't even complete my first year of CS because I wasn't learning as fast as I wanted. School teaches you theory anyways, a job will teach you how to apply it in the real world. Anyone who can read and has the slightest interest in programming can learn the theory by themselves. As for the different classes of programmers, I think the OP pushed more the extremes than the general cases. I came across a series of articles by Eric Lippert a few weeks ago talking about the matter: http://blogs.msdn.com/ericlippert/archive/tags/Cargo+Cult+Programming/default.aspx
Re: Writing a language parser in D
> I've ported boost::spirit to d. No idea if it does what you want, > but I've written some fairly complicated grammars with it. > > It's not a tool though, you just define your grammar directly in code. > Which is either a plus or a minus depending on your point of view. Thanks for all replies, Ellery, div0, Bill et. al. There's 101 odd productions in EBNF so whatever is the easiest to plug these directly into the tool or engine is probably the road of least resistance for this exercise.
Re: Writing a language parser in D
Justin Johansson wrote: > Can D people please recommend suitable tools for generating a parser (in D) > for an LL(1) grammar. There's bound to be much better parser generator tools > available nowadays, since my last foray into this area 10+ years ago with > YACC. I've heard of tools like bison, SableCC etc but apart from the names > know nothing about them. > > (Note. This question is not about writing a parser for D. It is about > writing a parser in D for another language which has an LL(1) grammar). > > Thanks in advance for all help. > > -- Justin Johansson > You might have a look at ANTLR. It's an LL(k) or LL(*) (versions) parser generator. I've found it suitable for writing a parser for D (yes I know), so it is definitely powerful enough. Currently, there is no implementation of ANTLR that generates D code, so if you really want a pure D parser, look elsewhere. However, I believe it can generate C, which you might be able to link to. If so, I'd say it's your best bet.
Re: Template Metaprogramming Made Easy (Huh?)
language_fan wrote: > Mon, 14 Sep 2009 07:33:59 -0400, bearophile thusly wrote: > >> But lot of people will judge D against more modern languages like C#, >> Scala or Java) and not against C. > > Programmers often belong to three kinds of groups. First come the fans of > traditionally weakly typed compiled languages (basic, c, c++). They have > tried some "dynamic" or "academic" languages but did not like them. They > fancy efficiency and close to metal feel. They think compilation to > native code is the best way to produce programs, and think types should > reflect the feature set of their cpu. They believe the syntax C uses was > defined by their God. > > The second group started with interpreted languages built by amateurs > (php, ruby, python, some game scripting language etc). They do not > understand the meaning the types or compilation. They prefer writing > short programs that usually seem to work. They hate formal specifications > and proofs about program properties. They are usually writing simple web > applications or some basic shareware utilies no one uses. They also hate > trailing semicolons. > > The members of the last group have studied computer science and > languages, in particular. They have found a pet academic language, > typically a pure one, but paradigms may differ. In fact this is the group > which uses something other than the hybrid object-oriented/procedural > model. They appreciate a strong, orthogonal core language that scales > cleanly. They are not scared of esoteric non-C-like syntax. They use > languages that are not ready to take a step to the "real world" during > the 70 next years. > That's a fancy way of saying that anyone who has not studied CS is a moron and therefore cannot understand what is good about languages, thus they lose any argument automatically. Am I right?
Re: Writing a language parser in D
On Mon, Sep 14, 2009 at 2:46 PM, div0 wrote: > -BEGIN PGP SIGNED MESSAGE- > Hash: SHA1 > > Justin Johansson wrote: >> Can D people please recommend suitable tools for generating a parser (in D) >> for an LL(1) grammar. There's bound to be much better parser generator >> tools available nowadays, since my last foray into this area 10+ years ago >> with YACC. I've heard of tools like bison, SableCC etc but apart from the >> names know nothing about them. >> >> (Note. This question is not about writing a parser for D. It is about >> writing a parser in D for another language which has an LL(1) grammar). >> >> Thanks in advance for all help. >> >> -- Justin Johansson >> > > I've ported boost::spirit to d. No idea if it does what you want, > but I've written some fairly complicated grammars with it. > > It's not a tool though, you just define your grammar directly in code. > Which is either a plus or a minus depending on your point of view. > > Quick intro: > > http://www.boost.org/doc/libs/1_36_0/libs/spirit/classic/index.html > > And D implementation: > > http://www.sstk.co.uk/spiritd.php I'm not seeing the powershell script or test app in that .zip file. I don't really need it, I was just curious what the syntax looked like without any operator overloading. --bb
Re: Writing a language parser in D
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Justin Johansson wrote: > Can D people please recommend suitable tools for generating a parser (in D) > for an LL(1) grammar. There's bound to be much better parser generator tools > available nowadays, since my last foray into this area 10+ years ago with > YACC. I've heard of tools like bison, SableCC etc but apart from the names > know nothing about them. > > (Note. This question is not about writing a parser for D. It is about > writing a parser in D for another language which has an LL(1) grammar). > > Thanks in advance for all help. > > -- Justin Johansson > I've ported boost::spirit to d. No idea if it does what you want, but I've written some fairly complicated grammars with it. It's not a tool though, you just define your grammar directly in code. Which is either a plus or a minus depending on your point of view. Quick intro: http://www.boost.org/doc/libs/1_36_0/libs/spirit/classic/index.html And D implementation: http://www.sstk.co.uk/spiritd.php - -- My enormous talent is exceeded only by my outrageous laziness. http://www.ssTk.co.uk -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iD8DBQFKrrmbT9LetA9XoXwRAg0ZAJ95oFr48DUbDEBGKUOCpWDNewYhGwCfQb83 ud7OQmiXnPmpAuRQdpLHyLc= =PPEc -END PGP SIGNATURE-
Writing a language parser in D
Can D people please recommend suitable tools for generating a parser (in D) for an LL(1) grammar. There's bound to be much better parser generator tools available nowadays, since my last foray into this area 10+ years ago with YACC. I've heard of tools like bison, SableCC etc but apart from the names know nothing about them. (Note. This question is not about writing a parser for D. It is about writing a parser in D for another language which has an LL(1) grammar). Thanks in advance for all help. -- Justin Johansson
Re: Floating point rounding modes: we should restrict them slightly
Brad Roberts wrote: Walter Bright wrote: strlen() is safe, while strcpy() and printf() are not. You sure? Does running beyond the bounds of the array if there's no null termination count as safe some how? :) Yes. Memory safety is defined as being free of memory corruption errors. Simply reading memory out of bounds does not corrupt memory. Note that it is ok for a memory safe program to generate a seg fault. printf() is not memory safe because of the %n format.
Re: Floating point rounding modes: we should restrict them slightly
Walter Bright wrote: > Don wrote: >> We could get close, I think. We could catch all violations in SafeD. >> Disallow calling core.stdc.fenv functions from inside SafeD modules, >> and provide an RAII object in std.math for changing the rounding mode. >> >> Actually there's probably a few other C functions we want to prohibit >> in SafeD -- the infamous string functions, for example. > > Yes, all the C functions will have to be gone through and separated. > strlen() is safe, while strcpy() and printf() are not. You sure? Does running beyond the bounds of the array if there's no null termination count as safe some how? :)
Re: Template Metaprogramming Made Easy (Huh?)
Mon, 14 Sep 2009 07:33:59 -0400, bearophile thusly wrote: > But lot of people will judge D against more modern languages like C#, > Scala or Java) and not against C. Programmers often belong to three kinds of groups. First come the fans of traditionally weakly typed compiled languages (basic, c, c++). They have tried some "dynamic" or "academic" languages but did not like them. They fancy efficiency and close to metal feel. They think compilation to native code is the best way to produce programs, and think types should reflect the feature set of their cpu. They believe the syntax C uses was defined by their God. The second group started with interpreted languages built by amateurs (php, ruby, python, some game scripting language etc). They do not understand the meaning the types or compilation. They prefer writing short programs that usually seem to work. They hate formal specifications and proofs about program properties. They are usually writing simple web applications or some basic shareware utilies no one uses. They also hate trailing semicolons. The members of the last group have studied computer science and languages, in particular. They have found a pet academic language, typically a pure one, but paradigms may differ. In fact this is the group which uses something other than the hybrid object-oriented/procedural model. They appreciate a strong, orthogonal core language that scales cleanly. They are not scared of esoteric non-C-like syntax. They use languages that are not ready to take a step to the "real world" during the 70 next years. So yes, every group has a bit different expectations.. >>C++ isn't anymore complex than D2,< > > I don't agree, see below. It would help all of you if you could somehow formally specify how you measure language complexity. Is it the length of the grammar definition or something else? Otherwise these are just subjective opinions.
Re: Template Metaprogramming Made Easy (Huh?)
Hello Lutger, That's cool, but scrapple is exactly that: an assortment of small(ish) projects / pieces of code that otherwise don't warrant a full project. If you feel like putting it online, just ping BCS and I'm sure he'll give you access right away. All I need is your dsource user name.
Re: shared adventures in the realm of thread-safety.
On Mon, 14 Sep 2009 07:44:44 -0400, Jason House wrote: Robert Jacques Wrote: On Sun, 13 Sep 2009 18:08:57 -0400, Jeremie Pelletier wrote: . Bartosz took the concept one step further: when declared as shared, all methods are implicitly wrapped in synchronize blocks. He then added a keyword for more manual, lock-free style programming. But this syntactic sugar isn't implemented yet. That is not the design for D2. shared means shared. It is neither meant to mean synchronized nor lockfree. I worry about optimization opportunities for shared in D2. There may be way too many memory fences in synchronized code. Without a mapping of a monitor to what's protected under a monitor, the compiler/optimizer's hands are tied. At best, every object will be its own monitor, but that hardly makes any sense... That is the Java model by the way. And really, no one knows what the shared design is for D2. The keyword has been added, but it has yet to be fleshed out. And once you start talking about how to flesh it out and what kinds of syntactic sugar are wanted/needed you need to start looking at previous solutions, which is what Bartosz has done in his blog posts. The specific issue you raise, that of excessive monitors, was addressed using the concept of unique/mobile objects which are both thread-safe and don't require locking. However, it appears that this won't make it into D2, which I feel is a shame.
Re: Non-moving generational GC [was: Template Metaprogramming Made Easy (Huh?)]
On Mon, 14 Sep 2009 09:39:51 -0400, Leandro Lucarella wrote: Jeremie Pelletier, el 13 de septiembre a las 22:58 me escribiste: [snip] I understand your points for using a separate memory manager, and I agree with you that having less active allocations make for faster sweeps, no matter how little of them are scanned for pointers. However I just had an idea on how to implement generational collection on a non-moving GC which should solve your issues (and well, mines too) with the collector not being fast enough. I need to do some hacking on I saw a paper about that. The idea was to simply have some list of objects/pages in each generation and modify that lists instead of moving objects. I can't remember the name of the paper so I can't find it now :S The problem with generational collectors (in D) is that you need read/write barriers to track inter-generational pointers (to be able to use pointers to younger generations in the older ones as roots when scanning), which can make the whole deal a little unpractical for a language that doesn't want to impose performance penalty to thing you wont use (I don't see a way to instrument read/writes to pointers to the GC only). This is why RC was always rejected as an algorithm for the GC in D, I think. my custom GC first, but I believe it could give yet another performance boost. I'll add my memory manager to my list of code modules to make public :) As a counter-point, objective-c just introduced a thread-local GC. According to a blog post (http://www.sealiesoftware.com/blog/archive/2009/08/28/objc_explain_Thread-local_garbage_collection.html) apparently this has allowed pause times similar to the pause times of the previous generational GC. (Except that the former is doing a full collect, and the later still has work to do) On that note, it would probably be a good idea if core.gc.BlkAttr supported shared and immutable state flags, which could be used to support a thread-local GC.
Non-moving generational GC [was: Template Metaprogramming Made Easy (Huh?)]
Jeremie Pelletier, el 13 de septiembre a las 22:58 me escribiste: > Tom S Wrote: > > > Jeremie Pelletier wrote: > > > Tom S Wrote: > > > > > >> Jeremie Pelletier wrote: > > >>> I myself allocate all my meshes and textures directly on the GC and I'm > > >>> pretty sure its faster than C's malloc and much safer. > > >> Hm, why would it be faster with the GC than malloc? I'm pretty sure it's > > >> the opposite :P Plus, I could use a specialized malloc implementation, > > >> like TLSF. > > > > > > The D GC is already specialized, and given its being used quite a lot in > > > D, there are good chances its already sitting in the CPU cache, its heap > > > already having the available memory block waiting on a freelist, or if > > > the alloc is more than 0x1000 bytes, the pages available in a pool. You'd > > > need to use malloc quite a lot to get the same optimal performance, and > > > mixing the two would affect the performance of both. > > > > It might be specialized for _something_, but it definitely isn't > > real-time systems. I'd say with my use cases there's a very poor chance > > the GC is sitting in the CPU cache since most of the time my memory is > > preallocated and managed by specialized structures and/or malloc. I've > > found that using the GC only for the hard-to-manually-manage objects > > works best. The rest is handled by malloc and the GC has a very shallow > > vision of the world thus its collection runs are very fast. Of course > > there's a drawback that both the GC and malloc will have some pages > > cached, wasting memory, but I don't let the GC touch too much so it > > should be minimal. YMMV of course - all depends on the memory allocation > > patterns of the application. > > I understand your points for using a separate memory manager, and > I agree with you that having less active allocations make for faster > sweeps, no matter how little of them are scanned for pointers. However > I just had an idea on how to implement generational collection on > a non-moving GC which should solve your issues (and well, mines too) > with the collector not being fast enough. I need to do some hacking on I saw a paper about that. The idea was to simply have some list of objects/pages in each generation and modify that lists instead of moving objects. I can't remember the name of the paper so I can't find it now :S The problem with generational collectors (in D) is that you need read/write barriers to track inter-generational pointers (to be able to use pointers to younger generations in the older ones as roots when scanning), which can make the whole deal a little unpractical for a language that doesn't want to impose performance penalty to thing you wont use (I don't see a way to instrument read/writes to pointers to the GC only). This is why RC was always rejected as an algorithm for the GC in D, I think. > my custom GC first, but I believe it could give yet another performance > boost. I'll add my memory manager to my list of code modules to make > public :) -- Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/ GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) Pack and get dressed before your father hears us, before all hell breaks loose.
Re: Floating point rounding modes: we should restrict them slightly
On Mon, 14 Sep 2009 16:44:48 +0400, Jason House wrote: Don Wrote: I've provided very simple solutions for both of these. I'm getting pretty irritated that people are acting as though these are difficult problems and trying to come up with convoluted solutions. Impose minimal semantics and it becomes trivial. FWIW, I've liked your proposals, but I don't feel qualified to comment. I never adjust rounding modes. I do like how I can be ignorant and get code that is better optimized. You've shown deep knowledge of floating point operation in the past, and I'm inclined to accept reasonable-sounding proposals from those that know way more than me. I second that. Nothing to add.
Re: Floating point rounding modes: we should restrict them slightly
Don Wrote: > > I've provided very simple solutions for both of these. I'm getting > pretty irritated that people are acting as though these are difficult > problems and trying to come up with convoluted solutions. Impose minimal > semantics and it becomes trivial. FWIW, I've liked your proposals, but I don't feel qualified to comment. I never adjust rounding modes. I do like how I can be ignorant and get code that is better optimized. You've shown deep knowledge of floating point operation in the past, and I'm inclined to accept reasonable-sounding proposals from those that know way more than me.
Re: shared adventures in the realm of thread-safety.
Robert Jacques Wrote: > On Sun, 13 Sep 2009 18:08:57 -0400, Jeremie Pelletier > wrote: > . > > Bartosz took the concept one step further: when declared as shared, all > methods are implicitly wrapped in synchronize blocks. He then added a > keyword for more manual, lock-free style programming. But this syntactic > sugar isn't implemented yet. > That is not the design for D2. shared means shared. It is neither meant to mean synchronized nor lockfree. I worry about optimization opportunities for shared in D2. There may be way too many memory fences in synchronized code. Without a mapping of a monitor to what's protected under a monitor, the compiler/optimizer's hands are tied. At best, every object will be its own monitor, but that hardly makes any sense...
Re: Template Metaprogramming Made Easy (Huh?)
Jeremie Pelletier: >I haven't had to use the C heap whatsoever so far in D, could you give me an >example of where you need it?< 1) I'm able to allocate a bigger single chunk of memory from the C heap, about 1.8 GB, while the GC heap of DMD on Windows allows only for a smaller chunk. In a program I've had to allocate a single chunk of memory. 2) I think the GC is faster at allocating small chunks of memory, while the C heap is faster at allocating large chunks. 3) GC-managed pointers have several restrictions (so much different that maybe I'd like them to be seen as a different type from the compiler, that requires a cast to be converted from/to C pointers. I don't know why this idea was not appreciated by D designers). One of them is that GC-managed pointers can't be tagged, you can't add one or two bits to GC-managed pointers, and such tags are useful when you want to implement certain data structures. >Indeed, and sometimes it's way faster than that.< But lot of people will judge D against more modern languages like C#, Scala 8or Java) and not against C. >C++ isn't anymore complex than D2,< I don't agree, see below. >I can't think of many features C++ has over D2. I can name quite a few >features D2 has over C++ :)< Complexity and not-simplicity come from many things, like corner cases, rules against rules against rules, unsafe things that the compiler isn't able to catch in case of programmer errors, unnatural syntax, and not just from features. For example the Python 3+ language has many more features than pure C, yet Python3 is simpler than C :-) >it still allows for dirty work to be done when you need it.< The less dirty you make it the better it will be when you try to mantain/debug your D code :-) >You don't need to code your application core in C and your application >behavior in a scripting language on top of the C core. D allows you to write >it all in one language with the same productivity, if not better productivity >for not having to write the abstraction layer between C and scripting.< While D is quite better than C, that of yours is a dream. In practice D isn't dynamic and for certain purposes D is not close to the "productivity" of Python :-) (Even just because in Python you can find tons of modules and bindings already done). There are ways to improve D still for such purposes. D can be more scalable as Scala :-) Bye, bearophile
Re: Floating point rounding modes: we should restrict them slightly
bearophile wrote: Walter Bright: Yes, all the C functions will have to be gone through and separated. strlen() is safe, while strcpy() and printf() are not. For some of the removed functions better C-like ones can be provided: http://www.ddj.com/cpp/214502214 Bye, bearophile Just use D instead.
Re: Floating point rounding modes: we should restrict them slightly
Walter Bright: > Yes, all the C functions will have to be gone through and separated. > strlen() is safe, while strcpy() and printf() are not. For some of the removed functions better C-like ones can be provided: http://www.ddj.com/cpp/214502214 Bye, bearophile
Re: Floating point rounding modes: we should restrict them slightly
Rainer Deyke wrote:
Don wrote:
The pure function memoisation issue:
Certain functions may be marked as 'pure', even though they use floating
point (and are therefore dependent on the FP state). The compiler must
be able to prevent memoisation of those functions in cases where the
rounding mode may have changed. (Or, equivalently, the memoisation must
include the FP state).
Don't forget that "uses floating point" is a transitive property. Any
pure function that calls a pure-but-unmemoisable function is itself
pure-but-unmemoisable.
This is incorrect. You've got it backwards. It's not "uses floating
point" that's the issue, it's "may use non-default floating point". A
memoisable floating point function can only use default floating point.
So, if it calls a non-memoisable pure function, it'll be using it in the
default state (even though that function can accept non-default state).
The transitivity propagates in the reverse direction: memoisability is
transitive, non-memoisability is not. Non-memoisable functions cannot
call memoisable ones without first ensuring that everything is back into
the default state.
The "pure" annotation is now used for two
related but different categories of functions with different properties,
and the compiler needs some way to keep track of which is which across
module boundaries. If the compiler can do that, then it can use the
same mechanism to differentiate between pure and non-pure functions, and
the "pure" annotation becomes redundant.
It's true that you could provide a similar loophole for any specific
global variable. But you'd need a *very* good reason.
Is there any real need to treat floating point state differently from
other global state in regard to "pure"?
Yes. Because it's all-pervasive. Unless you treat it specially, you
cannot use floating point in any pure function. That creates a
restriction which is so severe that 'pure' becomes useless. Something
like the following template function could not be pure:
T add(T a, T b) { return a + b; }
I do not believe that any other global state has an influence which is
in the same league.
Re: Floating point rounding modes: we should restrict them slightly
Don wrote: Walter Bright wrote: bearophile wrote: An important purpose of a not bug-prone language is remove as many undefined situations as possible. That's right. If you add that to D2 specs, can the compiler catch at compile time all cases of violations to that rule? Unlikely. But that has to be weighed against the former behavior being defined in a useless way. We could get close, I think. We could catch all violations in SafeD. Disallow calling core.stdc.fenv functions from inside SafeD modules, and provide an RAII object in std.math for changing the rounding mode. Actually there's probably a few other C functions we want to prohibit in SafeD -- the infamous string functions, for example. Yes, all the C functions will have to be gone through and separated. strlen() is safe, while strcpy() and printf() are not. I think the goal should be try to remove undefined behaviour from SafeD. Long term goal: "If a program uses no system modules other than those provided in the standard library, it should not be exposed to undefined behaviour." ? Right!
Re: Floating point rounding modes: we should restrict them slightly
Don wrote: > The pure function memoisation issue: > Certain functions may be marked as 'pure', even though they use floating > point (and are therefore dependent on the FP state). The compiler must > be able to prevent memoisation of those functions in cases where the > rounding mode may have changed. (Or, equivalently, the memoisation must > include the FP state). Don't forget that "uses floating point" is a transitive property. Any pure function that calls a pure-but-unmemoisable function is itself pure-but-unmemoisable. The "pure" annotation is now used for two related but different categories of functions with different properties, and the compiler needs some way to keep track of which is which across module boundaries. If the compiler can do that, then it can use the same mechanism to differentiate between pure and non-pure functions, and the "pure" annotation becomes redundant. Is there any real need to treat floating point state differently from other global state in regard to "pure"? -- Rainer Deyke - rain...@eldwood.com
Re: Floating point rounding modes: we should restrict them slightly
Walter Bright wrote: bearophile wrote: An important purpose of a not bug-prone language is remove as many undefined situations as possible. That's right. If you add that to D2 specs, can the compiler catch at compile time all cases of violations to that rule? Unlikely. But that has to be weighed against the former behavior being defined in a useless way. We could get close, I think. We could catch all violations in SafeD. Disallow calling core.stdc.fenv functions from inside SafeD modules, and provide an RAII object in std.math for changing the rounding mode. Actually there's probably a few other C functions we want to prohibit in SafeD -- the infamous string functions, for example. I think the goal should be try to remove undefined behaviour from SafeD. Long term goal: "If a program uses no system modules other than those provided in the standard library, it should not be exposed to undefined behaviour." ? D has something for the actions that must be done before the function exits, the scope(exit). Can something like that be used to automatically avoid undefined rounding situations? Using an RAII object to do it might be better. I agree. I'd like to do something similar with the floating point exception state, too. Haven't worked out the details yet.
Re: shared adventures in the realm of thread-safety.
Robert Jacques Wrote:
> On Sun, 13 Sep 2009 18:08:57 -0400, Jeremie Pelletier
> wrote:
>
> > Robert Jacques Wrote:
> >
> >> On Sun, 13 Sep 2009 15:04:57 -0400, Jeremie Pelletier
> >>
> >> wrote:
> >> [snip]
> >> > Unique data could only be used for aggregate properties,
> >> const/immutable
> >> > data would also be implicitly unique. This qualifier alone would
> >> > simplify shared quite a lot, allowing the use of unshared objects in
> >> > shared contexts safely.
> >>
> >> Neither const nor immutable data can be considered unique. First, any
> >> const data may be being mutated by another routine, so it can't be
> >> safely
> >> accessed without synchronization. Second, unique data is mutable while
> >> const/immutable data is not. Third, most implementations of unique allow
> >> for deterministic memory reclamation, which isn't possible if the unique
> >> data might actually be const/immutable.
> >
> > Good points, I can only agree with you here. However I still believe
> > immutable data should be able to be used in shared contexts without
> > being 'shared' or protected by a monitor.
>
> One of the purposes behind immutable was lock-free access. As far as I
> know you can use immutable data in shared contexts today without any other
> modifiers. A quick test seems to indicate this works today, but if you've
> got a test case where it doesn't, I'd recommend filing it as a bug.
Oh yeah, I'm confusing it with 'shared' methods not able to call 'const shared'
methods, which is a pain in the ass :(
> >> > The compiler should make the distinction between shared code and
> >> shared
> >> > data and allow both shared and unshared instances to use shared
> >> methods,
> >> > just like both const and mutable instances may call const methods. An
> >> > error should also be triggered when calling a shared method of a
> >> shared
> >> > object without synchronization, and maybe have a __sync keyword to
> >> > override this. If a synchronized method is called from a non-shared
> >> > object, no synchronization takes place.
> >>
> >> I think you have the wrong paradigm in mind. Shared and non-shared
> >> aren't
> >> mutable and const. They're mutable and immutable. From a technical
> >> perspective, synchronization of shared methods are handled by the
> >> callee,
> >> so there is no way not to call them and non-shared objects don't have a
> >> monitor that can be synchronized. Now you can have the compiler use the
> >> same code to generate two different object types (vtables, object
> >> layouts,
> >> etc) with have the same interface, but that doesn't sound like what
> >> you're
> >> suggesting.
> >
> > I know that shared/unshared is not const/mutable. What I meant is that
> > right now in D if a method is 'shared' it cannot be called from a
> > non-shared object, which makes unshared instance of the class unusable
> > without plenty of dirty casts. Take the following objects:
> >
> > class Foo { void foo() const; }
> > class Bar { void bar() shared; }
> >
> > Foo foo; foo.foo(); // ok, mutable object can call const method
> > Bar bar; bar.bar(); // error, unshared object may not call shared method
> >
> > I had only presented the concept, your idea of using two virtual tables
> > for shared/unshared instances is also what I had in mind for the
> > implementation, and it would give exactly the behavior I had in mind.
>
> Bartosz took the concept one step further: when declared as shared, all
> methods are implicitly wrapped in synchronize blocks. He then added a
> keyword for more manual, lock-free style programming. But this syntactic
> sugar isn't implemented yet.
The current D keywords (synchronized and shared) are already designed for that,
since synchronized implies shared. I don't want implicit synchronization, I'd
much rather have a shared class marking all its members/properties as shared
and letting me explicitely decide where the synchronization takes place.
> >> > Allow me to illustrate my point with some code:
> >> >
> >> > class Foo {
> >> > int bar() shared { return a; }
> >> > __sync bar2() { synchronized(this) return a; }
> >> > synchronized void foo() { a = 1; }
> >> > int a;
> >> > }
> >> > auto foo1 = new shared(Foo)();
> >> > auto foo2 = new Foo;
> >> >
> >> > foo1.foo(); // ok, synchronized call
> >> > synchronized(foo1) foo1.foo(); // warning: recursive synchronization
> >>
> >> Why a warning? Monitors are designed to handle recursive
> >> synchronization.
> >
> > Its a performance issue that can easily be avoided, but still generates
> > valid code.
>
> Really? Every public method that calls another public method (of the same
> object) results in recursive synchronization. And if your example was
> longer than a one liner, you'd also have to have recursive
> synchronization. There are ways to reduce recursive synchronization, like
> public wrappers of protected/private methods, but they are not always
Re: Floating point rounding modes: we should restrict them slightly
Stewart Gordon wrote: Don wrote: Floating point settings are just another case of the same thing, except that currently violations in relation to the former are allowed. There's a fundamental difference between them: the floating point settings are a hardware feature and it is IMPOSSIBLE to avoid them. Actually, you _can_ avoid changing the floating point settings in the course of an average program. But still The hardware dependency is still there, in every function which uses floating point. And the compiler must assume that dependency. You can choose not to use locale settings. Or, you can pass them as a parameter, which doesn't work for floating point settings. As long as it's the built-in arithmetic operators you're concerned about. Of course. There's nothing else to floating point, other than the built-in operators. And this is the problem with unconstrained rounding modes: they influence EVERYTHING. But that said, wrapping every arithmetic operation in a function to purify it of dependence on floating point settings wouldn't be ideal. It's worse than that. Every function which might call a function which might use floating point would have to pass the parameter. It doesn't work. Please do not get sidetracked on pure functions, it is orthogonal to this issue. I'm not sure about this. ISTM arithmetic operators are essentially pure functions, and so the compiler may treat them as such. No, they always depend on the FP settings, and assuming they are pure functions is not permitted in C, C++, or D. C allows the rounding mode to change at any time. This proposal: Rounding mode changes must only affect callees, not callers. The pure function memoisation issue: Certain functions may be marked as 'pure', even though they use floating point (and are therefore dependent on the FP state). The compiler must be able to prevent memoisation of those functions in cases where the rounding mode may have changed. (Or, equivalently, the memoisation must include the FP state). I've provided very simple solutions for both of these. I'm getting pretty irritated that people are acting as though these are difficult problems and trying to come up with convoluted solutions. Impose minimal semantics and it becomes trivial.
Re: Template Metaprogramming Made Easy (Huh?)
Nick B Wrote: > Jeremie Pelletier wrote: > > Tom S Wrote: > > > >> Jeremie Pelletier wrote: > >>> Tom S Wrote: > >>> > Jeremie Pelletier wrote: > > I myself allocate all my meshes and textures directly on the GC and I'm > > pretty sure its faster than C's malloc and much safer. > Hm, why would it be faster with the GC than malloc? I'm pretty sure it's > the opposite :P Plus, I could use a specialized malloc implementation, > like TLSF. > >>> The D GC is already specialized, and given its being used quite a lot in > >>> D, there are good chances its already sitting in the CPU cache, its heap > >>> already having the available memory block waiting on a freelist, or if > >>> the alloc is more than 0x1000 bytes, the pages available in a pool. You'd > >>> need to use malloc quite a lot to get the same optimal performance, and > >>> mixing the two would affect the performance of both. > >> It might be specialized for _something_, but it definitely isn't > >> real-time systems. I'd say with my use cases there's a very poor chance > >> the GC is sitting in the CPU cache since most of the time my memory is > >> preallocated and managed by specialized structures and/or malloc. I've > >> found that using the GC only for the hard-to-manually-manage objects > >> works best. The rest is handled by malloc and the GC has a very shallow > >> vision of the world thus its collection runs are very fast. Of course > >> there's a drawback that both the GC and malloc will have some pages > >> cached, wasting memory, but I don't let the GC touch too much so it > >> should be minimal. YMMV of course - all depends on the memory allocation > >> patterns of the application. > > > > I understand your points for using a separate memory manager, and I agree > > with you that having less active allocations make for faster sweeps, no > > matter how little of them are scanned for pointers. However I just had an > > idea on how to implement generational collection on a non-moving GC which > > should solve your issues (and well, mines too) with the collector not being > > fast enough. I need to do some hacking on my custom GC first, but I believe > > it could give yet another performance boost. I'll add my memory manager to > > my list of code modules to make public :) > Jeremie > > If the code is really usefull, why not offer it to the Tango team, for > formal inclusion in the next release ? > > Nick B Because I dropped support for D1 long ago. If either the Tango or Phobos team like my code once I publish it, they are free to adapt it for their runtime. I rewrote the GC from scratch and optimized over the past 2 years to support my custom D runtime. It cannot be used as-is with neither phobos or tango without either changing the public interface of the GC or rewriting every runtime routine calling into the GC. I would only release it to public domain as an example of how to implement a tracing generational non-moving GC. I still need to implement the generational part, but I got the general algorithm down on paper today so I should have it working sometime this week. I'm not a big fan of code licenses and therefore like to write most of my code myself, if only to learn how it works. I rarely mind people asking for my code either, so long as I get credited for it :)
