[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Leandro Lucarella leandro.lucare...@sociomantic.com changed: What|Removed |Added CC||wfunct...@hotmail.com --- Comment #134 from Leandro Lucarella leandro.lucare...@sociomantic.com 2013-05-30 04:54:25 PDT --- *** Issue 7251 has been marked as a duplicate of this issue. *** -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Jameson beatgam...@gmail.com changed: What|Removed |Added CC||beatgam...@gmail.com --- Comment #132 from Jameson beatgam...@gmail.com 2013-03-08 11:38:39 PST --- What's the status of this? I think this post hints at what I want to know: http://forum.dlang.org/post/k9cg21$132k$1...@digitalmars.com Did this actually get into 2.062? It doesn't seem so by the changelog. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #133 from bearophile_h...@eml.cc 2013-03-08 11:48:39 PST --- (In reply to comment #132) Did this actually get into 2.062? I don't think so. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Trass3r mrmoc...@gmx.de changed: What|Removed |Added CC||mrmoc...@gmx.de --- Comment #128 from Vladimir Panteleev thecybersha...@gmail.com 2011-04-15 02:14:17 PDT --- (In reply to comment #127) Thank you for your insight! So from a game's developers point of I need to know when the GC will run either by configuration or by manually driving it. You can disable automatic garbage collection and manually invoke a collection right now. Both allow me to run a frame with most of the AI and physics disabled to give more of the time to the collector. This won't work for multiplayer games where the game state must be kept in sync on all sides. Ideally the GC would be able to run in less time than a single frame (say 10-15ms for a 30fps game). Moving GCs are bound to be slower than the current one, but heap compaction probably doesn't need to happen as often as a simple GC run to reclaim memory. Taking away some amount of time every frame is also acceptable. For example spending 1ms of every frame to do 1ms worth of data movement or analysis for compacting would be a reasonable thing to allow, The current GC doesn't support incremental runs. Jeremie Pelletier has written a garbage collector some time ago which can do a shallow scan and only collect objects with no immediate references: http://pastebin.com/f7a3b4c4a --- Comment #129 from Trass3r mrmoc...@gmx.de 2011-07-18 05:15:44 PDT --- What's the status of this? Why is every patch marked obsolete? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #130 from Trass3r mrmoc...@gmx.de 2011-07-18 06:10:29 PDT --- (In reply to comment #126) Why not just add an additional garbage collector with this new implementation and leave the old one as it is and then developers can choose which one to use at link time. That's an excellent idea. I mean there are at least 3 GC improvement projects that need extensive testing: - this suggestion - https://github.com/dsimcha/druntime/wiki/Druntime-GC-Optimization-Fork - https://github.com/D-Programming-Language/druntime/tree/CDGC/src/gc -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #131 from David Simcha dsim...@yahoo.com 2011-07-18 08:54:57 PDT --- (In reply to comment #130) (In reply to comment #126) Why not just add an additional garbage collector with this new implementation and leave the old one as it is and then developers can choose which one to use at link time. That's an excellent idea. I mean there are at least 3 GC improvement projects that need extensive testing: - this suggestion - https://github.com/dsimcha/druntime/wiki/Druntime-GC-Optimization-Fork The GC optimization fork was relatively simple, low-hanging fruit optimizations. This was merged in a long time ago, and was in the 2.053 release. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Jacob Carlborg d...@me.com changed: What|Removed |Added CC||d...@me.com --- Comment #126 from Jacob Carlborg d...@me.com 2011-04-15 00:27:53 PDT --- Why not just add an additional garbage collector with this new implementation and leave the old one as it is and then developers can choose which one to use at link time. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Sean Cavanaugh worksonmymach...@gmail.com changed: What|Removed |Added CC||worksonmymach...@gmail.com --- Comment #127 from Sean Cavanaugh worksonmymach...@gmail.com 2011-04-15 01:40:35 PDT --- (In reply to comment #120) (In reply to comment #118) True, and it works tolerably well. To do a moving gc, however, you need more precise information. I don't want a moving GC. I want a fast GC. (I in this context means D users with the same requirements, mainly video game developers.) I understand the advantages of a moving GC - heap compaction allowing for an overall smaller managed heap etc., but I hope you understand that sacrificing speed for these goals is not an unilateral improvement for everyone. I am a game developer, and this thread is fairly fascinating to me, as memory management and good support for Intel SSE2(and AVX) or PowerPC VMX are two of the biggest issues to me when considering alternative languages or the question of 'will this language be suitable in the future'. The SSE problem seems workable with extern C'd C++ DLLs code to handle the heavy math, which leaves the GC as a big 'what does this mean' when evaluating the landscape. The reality is a lot of game engines allocate a surprising amount of memory at run time. The speed of malloc itself is rarely an issue as most searches take reasonably similar amount of time. The real problems with heavy use of malloc are thread lock contention in the allocator, and fragmentation. Fragmentation causes two problems: large allocation failures when memory is low (say 1 MB allocation when 30 MB is 'free'), and virtual pages are unable to be reclaimed due to a stray allocation or two within the page. Lock contention is solved by making separate heaps. Fragmentation is fought also fought by separating the heaps, but organizing the allocations coherently either time-wise or by allocation type where like sized objects pooled into a special pool for objects of that size. As a bonus fixed size object pools have const time for allocation, except when the pool has to grow, but we try real hard to pre-size these to the worst case values. On my last project we had about 8 dlmalloc based heaps and 15 fixed sized allocator pools, to solve these problems. I would greatly prefer a GC to compact the heap to keep the peak memory down, because in embeded (console) environments memory is a constant but time is fungible. VM might be available on the environments, but it isn't going to be backed by disk. Instead the idea of the VM is that it is a tool to fight fragmentation of the underlying physical pages, and to help you get contiguous space to work with. There is also pressure to use larger (64k, 1MB, 4MB pages) pages to keep the TLB lookups fast, which hurts even more with fragmentation. Tiny allocations holding onto these big pages prevents them from being reclaimed, which makes getting those allocations moved somewhere better pretty important. Now the good news is a huge amount of resources in a game do not need to be allocated into a garbage collected space. For the most part anything you send to the GPU data is far better off being written into its memory system and left alone. Physics data and Audio data have similar behaviors for the most part and can be allocated through malloc or aligned forms of malloc (for SSE friendlies). So from a game's developers point of I need to know when the GC will run either by configuration or by manually driving it. Both allow me to run a frame with most of the AI and physics disabled to give more of the time to the collector. A panic execution GC pass that I wasn't expecting is acceptable, provided I get notified of it, as I would expect this to be an indicator memory is getting tight to the point an Out of Memory is imminent. A panic GC is a QA problem as we can tell them where and how often the are occurring and they can in turn tell the designers making the art/levels that they need to start trimming the memory usage a bit. Ideally the GC would be able to run in less time than a single frame (say 10-15ms for a 30fps game). Taking away some amount of time every frame is also acceptable. For example spending 1ms of every frame to do 1ms worth of data movement or analysis for compacting would be a reasonable thing to allow, even if it was in addition to the multi-millisecond spikes at some time interval (30 frames, 30 seconds whatever). Making the whole thing friendly to having lots of CPU cores wouldn't hurt either. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #88 from bearophile_h...@eml.cc 2011-04-14 02:06:33 PDT ---
(In reply to comment #87)
1. distinguishing real pointers from might-be-a-pointer (such as you might get
from union { int a; void* p; }).
In C unions are not tagged, but in many C programs the programmer has
introduced some mean to tell apart at runtime what's inside the union, like a
first bit set in the pointer, a tag field in a struct where the union is, or a
tag value elsewhere in the program. So time ago I have suggested an optional
standard method useful fur unions, named something like onGC(...). It gets
called at runtime by the GC during when it scans the union instance, and in
some way tells the GC if a field is a pointer to follow (to call that onGC()
the GC has to know that something is a specific union in the first place).
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #89 from Walter Bright bugzi...@digitalmars.com 2011-04-14 02:23:28 PDT --- (In reply to comment #88) In order to support C compatibility, untagged unions must be supported by the type system and the GC. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #90 from bearophile_h...@eml.cc 2011-04-14 03:58:52 PDT --- (In reply to comment #89) (In reply to comment #88) In order to support C compatibility, untagged unions must be supported by the type system and the GC. Right, but this doesn't touch much what I have said. Many programs that use unions contain some mean at runtime to tell what's inside the union. This information is what onGC() uses. Where the onGC() union method is not present, or the union contents are otherwise unknown, the GC may fall back to being not precise and conservative. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #92 from David Simcha dsim...@yahoo.com 2011-04-14 06:04:04 PDT --- (In reply to comment #91) Yes and no. Consider right now (although I think David fixed this), we allocate a bit for every 16 bytes of a page, even if the whole page is a block. Yes, I did fix this. Now it's every 16 bytes for small (1 page) allocations and every page for large (= 1 page) allocations. 2. devise a 'state machine' instead that the gc executes for a type. The state machine has instructions like advance n bytes to the next pointer and the next pointer is ambiguous and execute the following sequence n times. This could be a viable solution, but I think all we need would be one descriptor type: offset x has bitmask Y repeated N times. where the offset is optional, and describes the offset from the previous bitmask. This is roughly what I did in my initial patches. The comments at the top of the file describe it in more detail. See http://d.puremagic.com/issues/attachment.cgi?id=488action=edit -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #93 from Leandro Lucarella llu...@gmail.com 2011-04-14 06:21:29 PDT --- You can take a look at my concurrent D GC (CDGC), which is also precise. It is based on the work done by nfx...@gmail.com (which is based on the work done by David Simcha). Here is the very modest (and not so useful) project page: http://www.llucax.com.ar/proj/dgc/ Remember Druntime use to have a branch with CDGC merged: http://www.dsource.org/projects/druntime/browser/branches/CDGC And here is a mini HOWTO to try CDGC (in Tango), but now that is merged, it's outdated if you use Tango trunk (in which case you just have to call bob with -g=cdgc), but in that post you can find the compiler patches too (which I think are the exact same nfx...@gmail.com did): http://llucax.com.ar/blog/blog/post/-4d1fefb4 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #95 from Steven Schveighoffer schvei...@yahoo.com 2011-04-14 12:25:48 PDT --- (In reply to comment #94) I think that covers things, except for handling ambiguous pointers. Can you explain why we care about ambiguous pointers? That is, shouldn't we just always consider that an ambiguous pointer is a pointer? Why do we need a separate designation? But I think it still consumes a lot of static storage. I suggest a state machine, which will consume roughly 1 byte per pointer in the type. I think a state machine would work. I especially like the ability to call another state machine program, that helps tremendously where types include other types, and inheritance. To optimize the state machine a bit, it might be good to include a compression feature where if you have just a dense bunch of pointer/value types, you give the state machine a bitmask. probably the worst case is an array of array references (which alternate between pointer and length). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #96 from Leandro Lucarella llu...@gmail.com 2011-04-14 12:32:49 PDT --- (In reply to comment #95) (In reply to comment #94) I think that covers things, except for handling ambiguous pointers. Can you explain why we care about ambiguous pointers? That is, shouldn't we just always consider that an ambiguous pointer is a pointer? Why do we need a separate designation? To allow moving collectors (you can't update a pointer that's not really a pointer). Anyway, this problem is taking care of in the implementation by nfxjfg, which Walter seem to keep ignoring, as he always did with this bug report and all the useful insight it have. I'm not saying the solution is the best, but it's completely ignored for no (publicly know reason). I'll unsubscribe now from this bug report, as it really makes me sick =) If you want to contact me, your know where to find me... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #97 from Andrei Alexandrescu and...@metalanguage.com 2011-04-14 13:00:36 PDT --- (In reply to comment #96) (In reply to comment #95) (In reply to comment #94) I think that covers things, except for handling ambiguous pointers. Can you explain why we care about ambiguous pointers? That is, shouldn't we just always consider that an ambiguous pointer is a pointer? Why do we need a separate designation? To allow moving collectors (you can't update a pointer that's not really a pointer). Anyway, this problem is taking care of in the implementation by nfxjfg, which Walter seem to keep ignoring, as he always did with this bug report and all the useful insight it have. I'm not saying the solution is the best, but it's completely ignored for no (publicly know reason). I'll unsubscribe now from this bug report, as it really makes me sick =) If you want to contact me, your know where to find me... That's a fairly random thing to say, particularly now that this bug report is again attracting interest. Walter has expressed a concern about the proposed implementation, which implies he's definitely not ignoring it. If you wanted to release some pent-up frustration accumulated from the past, fine. Otherwise, the reaction is rather irrational. It would be in everybody's interest (and it would definitely make you feel better) if you continued adding value to this discussion and code. Generally, after having accumulated more information on conservative vs. precise collectors, I think D must aim at being as precise as possible - no ifs and buts. So this report and patch must be taken to completion. I'll get back with some more comments. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #103 from Andrei Alexandrescu and...@metalanguage.com 2011-04-14 15:08:15 PDT --- (In reply to comment #102) (In reply to comment #100) (In reply to comment #99) (In reply to comment #98) The work on improving introspection should be done anyway. The trouble with using runtime introspection for this is it'll be slow, and the scanning of data needs to be really fast. I understand. That still means (and please correct me if I'm wrong) that the right place for specialized code should be at TypeInfo level. Also, I wonder if there's a need for a DSL. Wouldn't automatically-generated Typeinfo methods suffice? I don't really understand your comment. Are you saying the TypeInfo should do introspection at runtime to generate specialized data tables for the gc (obviously caching it so it is done only once per type)? This is certainly a possible approach. I was thinking that the compiler could generate D code that does the scanning instead of us defining a DSL for that. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #104 from Walter Bright bugzi...@digitalmars.com 2011-04-14 15:47:25 PDT --- (In reply to comment #103) I was thinking that the compiler could generate D code that does the scanning instead of us defining a DSL for that. That's a fascinating idea. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #105 from Andrei Alexandrescu and...@metalanguage.com 2011-04-14 16:00:24 PDT --- (In reply to comment #104) (In reply to comment #103) I was thinking that the compiler could generate D code that does the scanning instead of us defining a DSL for that. That's a fascinating idea. I think it's just a simple idea. You do generate code for constructors etc. already... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #106 from Walter Bright bugzi...@digitalmars.com 2011-04-14 16:25:11 PDT --- (In reply to comment #105) I think it's just a simple idea. You do generate code for constructors etc. already... The main challenge would be finding the fastest interface for it with the gc. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Vladimir thecybersha...@gmail.com changed: What|Removed |Added CC||thecybersha...@gmail.com --- Comment #107 from Vladimir thecybersha...@gmail.com 2011-04-14 16:36:48 PDT --- Am I the only one who is concerned with the performance implications of complicating the garbage collector any further, especially considering that precise heap scanning will not completely solve any problems? As far as the (small) drop in mean performance, I say who cares? *I* care. I already have solutions for false pointer problems. If I'm going to write an action video game in D, I sure as hell don't want the GC taking its sweet time while the player gets fragged due to screen lag. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #108 from David Simcha dsim...@yahoo.com 2011-04-14 17:08:48 PDT --- (In reply to comment #107) Am I the only one who is concerned with the performance implications of complicating the garbage collector any further, especially considering that precise heap scanning will not completely solve any problems? As far as the (small) drop in mean performance, I say who cares? *I* care. I already have solutions for false pointer problems. If I'm going to write an action video game in D, I sure as hell don't want the GC taking its sweet time while the player gets fragged due to screen lag. That's why heap allocations in real-time code are a bad idea. This patch won't change that. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #110 from bearophile_h...@eml.cc 2011-04-14 17:36:47 PDT --- (In reply to comment #109) (In reply to comment #108) That's why heap allocations in real-time code are a bad idea. This patch won't change that. Um, no, the GC is currently fast enough to scan a small heap within the timeframe of a video frame. Do you have a proof of this? Because currently the GC gets called when you allocate heap memory. And allocating heap memory (for objects, structs, dynamic arrays, closures, array concatenations, etc) between two frames of a fast video game is probably not a wise thing to do (today) in D. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #111 from Vladimir thecybersha...@gmail.com 2011-04-14 17:44:29 PDT --- (In reply to comment #110) Because currently the GC gets called when you allocate heap memory. Thanks for teaching me how garbage collectors work. I had no idea: http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf probably not a wise thing to do Empty words. Yes, I ran tests and benchmarks. The D GC is okay as it is now. There are efforts to make it faster, and I welcome them by all means. However, precise heap scanning will not solve any of my problems. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #112 from Walter Bright bugzi...@digitalmars.com 2011-04-14 17:48:22 PDT --- (In reply to comment #110) And allocating heap memory (for objects, structs, dynamic arrays, closures, array concatenations, etc) between two frames of a fast video game is probably not a wise thing to do (today) in D. Anything with hard realtime requirements cannot do allocation - even in C/C++, malloc() does not have an upper limit on its time. What is done is to pre-allocate everything necessary before entering the hard realtime section. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #113 from Vladimir thecybersha...@gmail.com 2011-04-14 18:00:14 PDT --- (In reply to comment #112) Anything with hard realtime requirements cannot do allocation - even in C/C++, malloc() does not have an upper limit on its time. What is done is to pre-allocate everything necessary before entering the hard realtime section. This does not apply to the discussion. Video games do not have hard-realtime requirements. Garbage collection speed dictates how much work must the programmer do to offset the GC's slowness. If the GC is fast enough that it does not cause performance issues on systems satisfying the game's minimum system requirements, the programmer doesn't need to care about it at all. Otherwise, they must do some work (the slower the GC, the more work) to reduce the size of the heap, or the number of allocations, or ultimately abandon heap allocation entirely. This might be easy in simple video games, but becomes increasingly painful in very large projects, with non-trivial user interfaces etc. So, by making the GC slower, you are creating more work for me. I am not happy about it. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #114 from David Simcha dsim...@yahoo.com 2011-04-14 18:23:13 PDT --- (In reply to comment #113) (In reply to comment #112) Anything with hard realtime requirements cannot do allocation - even in C/C++, malloc() does not have an upper limit on its time. What is done is to pre-allocate everything necessary before entering the hard realtime section. This does not apply to the discussion. Video games do not have hard-realtime requirements. Garbage collection speed dictates how much work must the programmer do to offset the GC's slowness. If the GC is fast enough that it does not cause performance issues on systems satisfying the game's minimum system requirements, the programmer doesn't need to care about it at all. Otherwise, they must do some work (the slower the GC, the more work) to reduce the size of the heap, or the number of allocations, or ultimately abandon heap allocation entirely. This might be easy in simple video games, but becomes increasingly painful in very large projects, with non-trivial user interfaces etc. So, by making the GC slower, you are creating more work for me. I am not happy about it. How about this: I can virtually guarantee that any slowness caused by precise heap scanning is more than offset by my recent patches (in Git but not in any DMD release yet). See https://github.com/dsimcha/druntime/wiki/Druntime-GC-Optimization-Fork . -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #117 from Vladimir thecybersha...@gmail.com 2011-04-14 19:06:29 PDT --- (In reply to comment #116) Yes, they do. It's called the frame rate. (Though I'd guess to be technical, this a soft-realtime requirement.) That's exactly what I meant. Hard realtime means that missing a deadline is equivalent to a complete system failure. Heap allocation is indeed not an option in that case. Why do you think the GC will get slower? One of the major points of a precise GC is that it does less total work than a conservative GC. Why? Because following a pointer, even if it goes nowhere, is an expensive operation (I'd guess O(log Heap_Size)) to say nothing of the cost of keeping around and tracing the excess garbage. And the more precision the GC has, the less pointers it has to trace per unit memory and the total memory traced is reduced as well. So it's win-win. I hope it is as you say it is, but without benchmarks it's hard to say anything, and this talk of state machines etc. is disconcerting. Note that the current GC does a quick check for each possible pointer if it's between the low and high address range of all GC pages - for small heaps, this weeds out most false pointers. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #118 from Walter Bright bugzi...@digitalmars.com 2011-04-14 19:34:40 PDT --- (In reply to comment #117) I hope it is as you say it is, but without benchmarks it's hard to say anything, and this talk of state machines etc. is disconcerting. Why? Also, even if the compiler emits the tables necessary for more precise gc, the gc implementation can ignore them and do it the old way. Emitting the tables makes it possible for people to experiment with various kinds of gc strategies. Note that the current GC does a quick check for each possible pointer if it's between the low and high address range of all GC pages - for small heaps, this weeds out most false pointers. True, and it works tolerably well. To do a moving gc, however, you need more precise information. BTW, I just want to reiterate that a hard realtime constraint means your program fails if it doesn't meet it. A soft constraint means the program degrades in some way, but keeps functioning. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #120 from Vladimir thecybersha...@gmail.com 2011-04-14 19:50:08 PDT --- (In reply to comment #118) I hope it is as you say it is, but without benchmarks it's hard to say anything, and this talk of state machines etc. is disconcerting. Why? It sounds slower. This is subjective and unscientific. That's why I said only a benchmark will show the real results. Also, even if the compiler emits the tables necessary for more precise gc, the gc implementation can ignore them and do it the old way. Emitting the tables makes it possible for people to experiment with various kinds of gc strategies. I would like to avoid bloating executables any further, and giving reverse engineers more data about my code. (I know executable size doesn't affect performance, at least in theory, but it does matter and can't be completely neglected either.) True, and it works tolerably well. To do a moving gc, however, you need more precise information. I don't want a moving GC. I want a fast GC. (I in this context means D users with the same requirements, mainly video game developers.) I understand the advantages of a moving GC - heap compaction allowing for an overall smaller managed heap etc., but I hope you understand that sacrificing speed for these goals is not an unilateral improvement for everyone. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #121 from David Simcha dsim...@yahoo.com 2011-04-14 19:59:28 PDT --- (In reply to comment #120) I understand the advantages of a moving GC - heap compaction allowing for an overall smaller managed heap etc., but I hope you understand that sacrificing speed for these goals is not an unilateral improvement for everyone. Since we don't have any hard benchmarks conveniently available, let's assume for the sake of argument that a precise/moving/etc. GC would be slower. Your case is a niche case and calls for a niche garbage collector implementation. D's GC is designed (IIRC) to allow selecting an implementation at link time. Eventually, someone could write a decent low-latency GC optimized for small heaps for game programmers. In the mean time, we could fork the current one. The stock GC, though, should handle the common cases, not a few game programmers' corner case. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Leandro Lucarella llu...@gmail.com changed: What|Removed |Added CC||llu...@gmail.com --- Comment #122 from Leandro Lucarella llu...@gmail.com 2011-04-14 20:06:11 PDT --- (In reply to comment #121) (In reply to comment #120) I understand the advantages of a moving GC - heap compaction allowing for an overall smaller managed heap etc., but I hope you understand that sacrificing speed for these goals is not an unilateral improvement for everyone. Since we don't have any hard benchmarks conveniently available, let's assume for the sake of argument that a precise/moving/etc. GC would be slower. Your case is a niche case and calls for a niche garbage collector implementation. D's GC is designed (IIRC) to allow selecting an implementation at link time. Eventually, someone could write a decent low-latency GC optimized for small heaps for game programmers. In the mean time, we could fork the current one. The stock GC, though, should handle the common cases, not a few game programmers' corner case. You mean like this one (except it's not optimized for small heaps, just for small pauses and works)? http://llucax.com.ar/blog/blog/post/-1a4bdfba PS: Yeah, for some reason I still get the e-mails even when I removed myself from te Cc =/ -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #123 from Vladimir thecybersha...@gmail.com 2011-04-14 20:09:13 PDT --- (In reply to comment #121) Your case is a niche case and calls for a niche garbage collector implementation. I would like to ask you to reconsider that opinion. Please take into consideration the size of the video game industry, including that for consoles and mobile devices. Also, keep in mind that a good amount of hype regarding D was generated by video games written in it - starting with Kenta Cho's old OpenGL ones, as well as that commercial D strategy game I can't find at the moment. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #124 from Walter Bright bugzi...@digitalmars.com 2011-04-14 20:26:14 PDT --- (In reply to comment #122) PS: Yeah, for some reason I still get the e-mails even when I removed myself from te Cc =/ Just when I thought I was out... they pull me back in! -- Michael Coreclone, The D Father Part III -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #125 from Walter Bright bugzi...@digitalmars.com 2011-04-14 20:33:11 PDT --- (In reply to comment #120) I understand the advantages of a moving GC - heap compaction allowing for an overall smaller managed heap etc., but I hope you understand that sacrificing speed for these goals is not an unilateral improvement for everyone. In a gc, speed really is the paramount consideration. (The problem with excessive memory consumption is speed, after all.) Unfortunately, the speed of any gc strategy cannot be determined in advance. One has to try it, profile it, and tune it to see if it is an overall improvement. The theoretical speed improvement of more precise gc comes from: 1. the collector doing less work because it knows where the actual pointers are rather than having to scan for them 2. not following and scanning memory that is falsely pointed to by an integer 3. reducing the working set of memory, meaning less work for scanning The theoretical speed decrease comes from: 1. more work to read the pointer tables 2. possibly a large hit from using a virtual function How this will play out will require actually trying it. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
Walter Bright bugzi...@digitalmars.com changed:
What|Removed |Added
CC||bugzi...@digitalmars.com
--- Comment #87 from Walter Bright bugzi...@digitalmars.com 2011-04-13
21:51:35 PDT ---
The idea, as I understand it, is to supply a bit mask of where the pointers
are. For me, the difficulties are:
1. distinguishing real pointers from might-be-a-pointer (such as you might get
from union { int a; void* p; }).
2. large static arrays, large structs/classes, structs with large static array
members, etc.
The amount of static data dedicated to such bit arrays could get very large.
I see two solutions:
1. if it is case (1) or (2), give up for that type and revert to the current
method of scanning that object
2. devise a 'state machine' instead that the gc executes for a type. The state
machine has instructions like advance n bytes to the next pointer and the
next pointer is ambiguous and execute the following sequence n times.
I don't see an obvious choice which is better.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #83 from bearophile_h...@eml.cc 2010-11-15 04:43:23 PST --- (In reply to comment #82) Anyway, unfortunately DMD development model still sucks, it sucks much less than... let's say 2 years ago, but... Walter is willing to slowly improve his practices. Do you have a list of suggestions? If you show this list on the main D newsgroup he might pick something from it. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #84 from Leandro Lucarella llu...@gmail.com 2010-11-15 04:47:48 PST --- (In reply to comment #83) (In reply to comment #82) Anyway, unfortunately DMD development model still sucks, it sucks much less than... let's say 2 years ago, but... Walter is willing to slowly improve his practices. Do you have a list of suggestions? If you show this list on the main D newsgroup he might pick something from it. I (and others) already suggested him how to improve things, a few really basic examples that come to my mind right now: * Tag releases in svn * Give feedback to people wanting to contribute -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #85 from bearophile_h...@eml.cc 2010-11-15 09:33:56 PST --- (In reply to comment #84) I (and others) already suggested him how to improve things, Keep suggesting those things. Sometimes you have to say something five times to Walter. * Tag releases in svn Explain him why this is useful. * Give feedback to people wanting to contribute Maybe he doesn't fully understand why contributions from other people are important. Showing him some examples is useful. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #86 from Leandro Lucarella llu...@gmail.com 2010-11-15 09:44:18 PST --- (In reply to comment #85) (In reply to comment #84) I (and others) already suggested him how to improve things, Keep suggesting those things. Sometimes you have to say something five times to Walter. * Tag releases in svn Explain him why this is useful. * Give feedback to people wanting to contribute Maybe he doesn't fully understand why contributions from other people are important. Showing him some examples is useful. This is getting a little off-topic here, but I think I'll focus on other projects, is too much effort. I agree that Walter has improved a little, but the ratio results/efforts is *really* low still, and it doesn't worth it for me any more. I hate sounding like a broken record... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #81 from nfx...@gmail.com 2010-11-14 18:06:05 PST --- I obsoleted all the patches because they were outdated (too old dmd/Tango versions). I don't think it's very efficient to make new patches and post them here (I mean, there are already 21 obsoleted patches, and this issue has probably the most comments on bugzilla, despite not much going on). Please send me an email to request newer patches. These patches include: * dmd patch for PointerMap output (backwards compatible to old Phobos etc.) * Tango patch to include PointerMap in object.d, and to make use of them in gcx.d * additional dmd patch to make associative array scanning precise (changes ABI to include more type info; again completely backwards compatible to Phobos) * additional Tano patch to make associative array scanning precise (backwards compatible) The obsoleted patches will only apply to old dmd versions, and what's worse, only if you run unix2dos on all dmd source files beforehand. (The line endings in the dmd.zip are inconsistent, and the dmd svn is unusable because releases are not tagged properly.) Btw. I didn't really appreciate Walter's 64 bit changes to the AA ABI. Really, the ABI should pass all TypeInfos to the AA functions. If my patch is applied, dmd supports roughly 3 AA ABIs, which is very silly. If someone has a better idea how to keep track of the patches and so on (that are better than flooding bugzilla or emailing me), please make a suggestions. Last but not least: [02:55:20] wm4 AndreiAlexandres: also, I'm about to post new patches for precise gc scanning (update to newer dmd versions) to issue 2463 on bugzilla; is there some better way to participate on D/dmd development than to continuously post patches to bugzilla that are going to be ignored [02:57:07] * AndreiAlexandres has quit (Quit: AndreiAlexandres) It could be a bad coincidence, or show how fabulously awesome the D development model is. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #82 from Leandro Lucarella llu...@gmail.com 2010-11-14 19:17:59 PST --- Maybe you should try with LDC's or GDC's issues trackers, as this is an implementation detail maybe it gets better reception there (but it would be hard to get accepted there since both uses DMDFE and it would mean to fork it). When I want to keep patches easily updated I use git (git svn in this case). But then, the lack of tagging in DMD's svn can be annoying. Anyway, unfortunately DMD development model still sucks, it sucks much less than... let's say 2 years ago, but... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #80 from nfx...@gmail.com 2010-09-16 11:26:43 PDT --- By the way, if the patch is going to be accepted, it would probably be good to get rid of the NO_SCAN flags. Instead, NO_SCAN should be detected by examining the PointerMap. A PointerMap with length 0 could take over the NO_SCAN meaning. E.g.: Old code: bool is_NO_SCAN = !(typeinfo.flags() 1); New code: bool is_NO_SCAN = typeinfo.pointermap().bits.length == 0; Then you don't need to provide/pass around the TypeInfo.flags() anymore. Would get rid of some uglyness. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #77 from nfx...@gmail.com 2010-09-15 02:22:03 PDT --- There's a small bug in the memory clearing in mallocNoSync(), that could cause memory leaks. Will post patch on request (nobody is using this anyway, right?). Also, I found out that that SENTINEL is dead code. Uncommenting the debug = SENTINEL; line on start of gcx.d will not include the code in version(SENTINEL) blocks, because debug identifiers and version identifiers live in different namespaces. Makes me wonder, does anyone ever use the SENTINEL stuff for testing? Or just thought he'd be using it? Btw. someone said 16 bytes is the minimum alignment on OSX, so SENTINEL is broken there anyway. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #78 from Leandro Lucarella llu...@gmail.com 2010-09-15 05:51:08 PDT --- (In reply to comment #77) There's a small bug in the memory clearing in mallocNoSync(), that could cause memory leaks. Will post patch on request (nobody is using this anyway, right?). I ported it to my GC, so I'm interested in knowing what the bug is about to check if I have it too. Also, I found out that that SENTINEL is dead code. Uncommenting the debug = SENTINEL; line on start of gcx.d will not include the code in version(SENTINEL) blocks, because debug identifiers and version identifiers live in different namespaces. Makes me wonder, does anyone ever use the SENTINEL stuff for testing? Or just thought he'd be using it? Btw. someone said 16 bytes is the minimum alignment on OSX, so SENTINEL is broken there anyway. Yeah, I think most of the versioned code is dead or close to it, because I doubt anybody test it. In my GC, which makes SENTINEL and MEMSTOMP run-time configurations, SENTINEL is broken and I didn't had the time to fix it yet. MEMSTOMP seems to work though. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #79 from nfx...@gmail.com 2010-09-15 06:33:39 PDT ---
Incremental patch:
diff --git a/tango/core/rt/gc/basic/gcx.d b/tango/core/rt/gc/basic/gcx.d
index 93c8078..0f049d7 100644
--- a/tango/core/rt/gc/basic/gcx.d
+++ b/tango/core/rt/gc/basic/gcx.d
@@ -589,9 +589,9 @@ class GC
// Return next item from free list
gcx.bucket[bin] = (cast(List*)p).next;
if( !(bits BlkAttr.NO_SCAN) )
-cstring.memset(p + size, 0, binsize[bin] - size);
+cstring.memset(p + request_size, 0, capacity - request_size);
//debug(PRINTF) printf(\tmalloc = %x\n, p);
-debug (MEMSTOMP) cstring.memset(p, 0xF0, size);
+debug (MEMSTOMP) cstring.memset(p, 0xF0, request_size);
}
else
{
request_size is the size the user requested, while size is request_size + the
pointermap's size. But size can be much smaller than memory block's real size
(= capacity), so you really want to start clearing the memory right after the
user data.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #739 is|0 |1 obsolete|| --- Comment #72 from nfx...@gmail.com 2010-09-09 06:36:26 PDT --- Created an attachment (id=751) D1 - patch for dmd for creating pointer bitmasks -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #737 is|0 |1 obsolete|| --- Comment #73 from nfx...@gmail.com 2010-09-09 06:37:13 PDT --- Created an attachment (id=752) D1 - patch for Tango's runtime to enable precise GC scanning -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #74 from nfx...@gmail.com 2010-09-09 06:41:46 PDT --- Created an attachment (id=753) dmd: enable precise scanning for AAs AAs are special because they use some runtime mechanism. dmd didn't allow precise scanning because not all type information was available (usually only the key). This patch completely changes the runtime interface for AAs in order to allow precise scanning. It also does much much more. (For example I didn't like that dmd's runtime interface was so incredibly whacky, such as passing values of arbitrary runtime type per vararg, and expecting the value next to the argument before on the stack. Walter probably has to change this anyway for the dmd 64 bit port...) The patched dmd is backwards compatible and compiles Tango svn just fine. The patched Tango tells dmd to use the new ABI by declaring a magical member variable somewhere in object.di. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #75 from nfx...@gmail.com 2010-09-09 06:43:43 PDT --- Created an attachment (id=754) tango: enable precise scanning for AAs This is the Tango patch that goes with the dmd patch (attachment 753). The AA implementation is duplicated because the Tango patch is as well compatible with an unpatched dmd. An unpatched dmd will compile the old AA implementation instead of the new one. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #488 is|0 |1 obsolete|| --- Comment #76 from nfx...@gmail.com 2010-09-09 06:45:13 PDT --- (From update of attachment 488) marking dsimcha's patches as obsolete because there are way too many attachments already, and it seems it's not going to be used (even less than my patches anyway) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #701 is|0 |1 obsolete|| --- Comment #69 from nfx...@gmail.com 2010-08-24 01:37:05 PDT --- Created an attachment (id=737) D1 - patch for Tango's runtime to enable precise GC scanning Same as old patch, updated to newer tango svn. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #70 from nfx...@gmail.com 2010-08-24 01:40:52 PDT --- Created an attachment (id=738) experiment: use ClassInfo to get bitmask for object allocations objbitmask.patch is a patch on top of tango_precise_gc.patch, which makes storing the pointer bitmap inline unnecessary. Instead, it assumes that all memory blocks flagged with BlkAttr.FINALIZE are D objects, and uses their ClassInfo to get the bitmask. Seems to be slightly slower, but also reduces space overhead. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #700 is|0 |1 obsolete|| --- Comment #71 from nfx...@gmail.com 2010-08-24 06:26:56 PDT --- Created an attachment (id=739) D1 - patch for dmd for creating pointer bitmasks don't emit pointer maps for NO_SCAN types (breaks the test program pm.d included in the other post) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #68 from Leandro Lucarella llu...@gmail.com 2010-08-15 07:24:36 PDT --- More analysis on wasted space (for the current GC and for the precise patch) here: http://www.llucax.com.ar/blog/blog/post/098ceae8 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #67 from Leandro Lucarella llu...@gmail.com 2010-08-08 08:10:19 PDT --- Sor(In reply to comment #66) http://www.llucax.com.ar/blog/blog/post/1490c03e That page shows me a spectacularly complex page of Python error messages. Sorry about that, fixed! -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #61 from Leandro Lucarella llu...@gmail.com 2010-07-28 12:23:01 PDT --- (In reply to comment #60) Created an attachment (id=701) [details] D1 - patch for Tango's runtime to enable precise GC scanning - lots of nasty refactoring in gcx.d: Even when I agree that the GC needs a lot of refactoring, I don't think it's a good idea to include it in this patch, it makes much harder to understand it and it might introduce some subtle bugs that will be very hard to track down in so many changes. I'm working on a GC that was based on the Tango (0.99.9) GC and doing a lot of refactoring myself. The refactoring of things introduced by the patch looks really nice though. Also, shouldn't functions like freeNoSync check for interior pointers? What happens if you call it with such a pointer? I don't think so, it should be undefined behavior (based on C's free()). Thanks! -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #64 from Leandro Lucarella llu...@gmail.com 2010-07-28 13:04:07 PDT --- (In reply to comment #62) (In reply to comment #61) Even when I agree that the GC needs a lot of refactoring, I don't think it's a good idea to include it in this patch, it makes much harder to understand it and it might introduce some subtle bugs that will be very hard to track down in so many changes. I have to agree, but I did these changes in order to make storing a bitmask configurable, and to properly support SENTINEL. The changes the original patch did weren't very small either. I see 4 options: 1. keep this anyway 2. keep the old gcx.d around and apply the changes to a new incarnation of gcx.d, and let the user choose the GC implementation at startup or compile time 3. only accept the compiler patch, and wait for Leandro's new GC 4. revert to the previous version of my patch (of course I wouldn't like this at all) Which is it? I think this should be replied by whoever have the authority to merge the patches, my comments were just wishes (and you made them true in a much higher proportion that I was expecting :). I'd say 1 is OK. About my GC, is a research work and, even when my goal is something realistic and I'm doing performance tests all the time, don't expect much. :) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #57 from Leandro Lucarella llu...@gmail.com 2010-07-27 21:19:01
PDT ---
I think there is a not-so-important bug in the DMD patch, the bits.length value
looks like it needs to be divided by size_t.sizeof (which is odd, since in the
patch it looks like it's already done in setSize()).
See this test program:
---
extern (C) int printf(char*, ...);
struct Test
{
int x;
void* p;
char[15] s;
Test* t;
long l;
union U {
int* pi;
int i;
}
U u;
}
void main()
{
Test* t = new Test;
printf(sizeof = %zu\n, Test.sizeof);
auto pm = typeid(Test).pointermap.bits;
printf(PointerMap: ptr = %p, length = %zu, T words = %zu, scan bits =
%zx, ptr bits = %zx\n,
pm.ptr, pm.length, pm[0], pm[1], pm[2]);
}
---
The output is:
PointerMap: ptr = 0x805ab1c, length = 12, T words = 10, scan bits = 242, ptr
bits = 42
All looks nice except for the length value, which should be 3 instead of 12.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #58 from Leandro Lucarella llu...@gmail.com 2010-07-27 21:23:34 PDT --- And another small comment about the Tango runtime patch, you add a binSize() function, but there is already a binsize[] array for the same purpose, you can remove the binSize(bin) function and replace it with binsize[bin]. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #698 is|0 |1 obsolete|| --- Comment #59 from nfx...@gmail.com 2010-07-27 22:49:51 PDT --- Created an attachment (id=700) D1 - patch for dmd for creating pointer bitmasks You're right, I stupidly write the byte length, not the array length. This patch fixes it and also eliminates two warnings about void* arithmetic. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #48 from Leandro Lucarella llu...@gmail.com 2010-07-25 17:04:56 PDT --- Well timings for dil are much worse :( This is dil generating the Tango docs, without precise scanning (dmd with the last patch, Tango unpatched): 52.01 53.73 52.21 51.79 50.58 52.62 53.01 48.49 51.51 49.68 min = 48.49 mean = 51.563, std = 1.58236847795 max = 53.73 And this is with precise scanning: 79.47 69.81 72.27 67.12 68.34 83.85 65.28 75.17 77.76 74.73 min = 65.28 mean = 73.38, std = 5.91698309013 max = 83.85 I can't explain why is even less stable with precise scanning, maybe is something to do with it being less cache-friendly. I don't know either why is so stable without precise scanning, when in other tests I've done it wasn't like that. Maybe the majority of false positives are from the static memory and the binary was placed in an address that make them less probable (the binary address doesn't change between runs). It would be nice if other people give this patches a try, specially with programs that have problems with false positives... Here are the profiling results (using perf[1]): Non-precise scanning: http://pastebin.com/zRKyc9mW Precise scanning: http://pastebin.com/jPJZLL8p It looks like findPool() might be used much more often than before? For example, I noticed the mixin code calls findPool() very early, so maybe it's being called in some situations where it's not necessary. Also, with the patch sizeOf() needs to call findPool(), but I don't think that should make a lot of difference (unless is used by the runtime very often for array manipulation). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #50 from Leandro Lucarella llu...@gmail.com 2010-07-25 17:30:20 PDT --- (In reply to comment #48) It looks like findPool() might be used much more often than before? For example, I noticed the mixin code calls findPool() very early, so maybe it's being called in some situations where it's not necessary. Also, with the patch sizeOf() needs to call findPool(), but I don't think that should make a lot of difference (unless is used by the runtime very often for array manipulation). Seeing the callgraph, 95% of the findPool() calls are being made directly from mark(), 4.5% from fullcollectshell(). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #45 from Leandro Lucarella llu...@gmail.com 2010-07-24 20:08:30
PDT ---
Well, I've made a little benchmark for the patch.
I'm using the voronoi[1] benchmark, since I think is a good GC benchmark,
because it exercises the GC a lot, but it does real work with the data (unlike
the typical tree benchmark). I find it particularly interesting too because
it seems to have a lot of false positives, making the runtime very bound to the
addresses returned by mmap(), as shown in the post[2] mentioned earlier in this
comments. This benchmarks confirmed that the high variance in runtime presented
by this test is due to false positives.
[1] http://codepad.org/xGDCS3KO
[2] http://www.llucax.com.ar/blog/blog/post/-7a56a111
I've compared 3 binaries, one compiled without any of this patches
(voronoi-dnp-tnp, i.e. Dmd Not Precise, to be honest, this is DMD 1.062
distributed by DigitalMars), one compiled with a patched DMD, but unpatched
Tango to see if the PointerMaps created by the compiler has any effect on
performance (voronoi-dp-tnp) and one compiled with both patched DMD and Tango
(voronoi-dp-tp). Patched DMD is svn r580 (D1 branch), Tango is svn trunk r5505,
and the patches are not the latest ones, are the previous (sorry, I was working
on this before you came up with the new patch, I'll try the new patch when I
have some time).
Anyway, here are the result:
$ for i in {1..10}; do /usr/bin/time -f%e ./voronoi-dnp-tnp -n 3; done
3.88
3.71
4.28
3.89
3.78
3.63
3.81
4.36
3.82
3.89
min = 3.63
mean = 3.905, std = 0.234343053378
max = 4.36
$ for i in {1..10}; do /usr/bin/time -f%e ./voronoi-dp-tnp -n 3; done
3.74
3.87
3.69
3.91
4.33
4.07
4.26
4.08
3.78
4.32
min = 3.69
mean = 4.005, std = 0.241994031148
max = 4.33
$ for i in {1..10}; do /usr/bin/time -f%e ./voronoi-dp-tp -n 3; done
4.05
4.03
4.04
4.03
4.02
4.02
4.02
4.02
4.02
4.05
min = 4.02
mean = 4.03, std = 0.0124721912892
max = 4.05
The differences between the patched an unpatched DMD doesn't look relevant,
specially taking into account the high variance and that they are not even the
same DMD version.
Unfortunately the patched GC fall a little (~3%) behind the unpatched one,
mean-wise, and a little more if we look at the min (about 10%), but the max
drops about the same (~7%) and the variance drops dramatically (~240%) with the
patched GC. Considering the precise scanning patch is the first try, and not
very optimized, it looks like a tradeoff that worth paying while trying to
improve this timings.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #43 from nfx...@gmail.com 2010-07-23 11:39:19 PDT --- You're right, there seem to be some places where the bitmask size is added or substracted twice. I don't really know; I took that code over from dsimcha's patch without modification. I was just thankful that I hadn't to write this code. I fixed the three issues you found. It seems to work, though I'm not 100% sure if it's correct now. Regarding moving collectors: I think this would be an interesting experiment and worth trying. My patch now has a second bitmask, where each bit tells whether a word is a moveable pointer or not. Instead of a second bitmap, you could just have a per-memory block flag that tells whether a memory block is a void[] and/or contains unions with pointers. (If the flag is set, the GC won't change any pointers inside the block.) You could maintain that flag as additional bitmap (along NOSCAN etc). This way storing small bitmaps inline would be simpler. Unions or fixed-size void[] are probably seldom enough to justify this simplification. gcx.d can choose either way to implement it using the compiler generated bitmasks. Before actually implementing a moving GC, one should experiment how many pinned pointers the stack/manually added ranges/unmovable pointers/datasegment generate and how they would fragment the heap. Also note that some runtime parts are not ready yet for a moving GC, such as Object.toHash. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #44 from Leandro Lucarella llu...@gmail.com 2010-07-23 12:15:44 PDT --- (In reply to comment #43) You're right, there seem to be some places where the bitmask size is added or substracted twice. I don't really know; I took that code over from dsimcha's patch without modification. I was just thankful that I hadn't to write this code. I fixed the three issues you found. It seems to work, though I'm not 100% sure if it's correct now. Thanks! Regarding moving collectors: I think this would be an interesting experiment and worth trying. My patch now has a second bitmask, where each bit tells whether a word is a moveable pointer or not. Instead of a second bitmap, you could just have a per-memory block flag that tells whether a memory block is a void[] and/or contains unions with pointers. (If the flag is set, the GC won't change any pointers inside the block.) You could maintain that flag as additional bitmap (along NOSCAN etc). This way storing small bitmaps inline would be simpler. Unions or fixed-size void[] are probably seldom enough to justify this simplification. gcx.d can choose either way to implement it using the compiler generated bitmasks. Yes, that can be a nice optimization if void[] and unions are rare. Before actually implementing a moving GC, one should experiment how many pinned pointers the stack/manually added ranges/unmovable pointers/datasegment generate and how they would fragment the heap. Yup! This patch opens that posibility too! Which is great. Also note that some runtime parts are not ready yet for a moving GC, such as Object.toHash. Yes, this is just a step in the right direction, not a final solution. Thanks again! A bikeshed suggestion, maybe it would be better to call PointerMap methods this way: isPointerAt() - mustScanWordAt() isMoveablePointerAt() - isPointerAt() hasUnmoveablePointers() - canUpdatePointers() Because the pointers are not moveable, the memory they point at is the one moveable or not. The pointer, if really pointer, are updateable, and if they are not guaranteed to be pointers, we shouldn't call them that. That's why I think is clearer to call a may be pointer a word that should be scanned and a guaranteed pointer (which the GC could update) simply a pointer. By the same means, I'd call pointer_bits and mpointer_bits scan_bits and pointer_bits respectively. BTW, there is already a GC attribute called NO_MOVE, which follows this nomenclature (is supposed to be used for blocks that can't be moved, not for blocks which pointers can't be updated). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #37 from Leandro Lucarella llu...@gmail.com 2010-07-22 17:54:38 PDT --- BTW, I just realized that this type information scheme doesn't enable the GC to move data around (i.e. it doesn't open the door to moving collectors) since the distinction between *is* a pointer and *may be* a pointer is not present. This difference is necessary for knowing when you can move things around, since a block pointed to by a *may be* a pointer should be pinned, because you can't update the word suspected to be a pointer (because in case is not, you are corrupting user's memory). Only block pointed to by *is* a pointer words are candidates for moving. Maybe considering that this involves a change in the compiler, it would be a good opportunity to finally open the door to moving collectors. Unfortunately this means more type information is necessary. Maybe 2 bitmasks can be used, a scan mask (that can take over the NO_SCAN attribute) and a pointer mask. A word marked as scan (i.e. scan bit == 1) should be scanned but might be a pointer or not (like the current bitmask proposed in this patch); a word marked pointer (i.e. pointer bit == 1) is guaranteed to be a pointer and the GC is allowed to update it if the pointed to block is moved. So a real pointer should have both scan and pointer set to 1 (yeah, scan is redundant, but I can't think of a better representation), and an union should have only scan set to 1. I don't know what to do with void* though, since is very common to use it as a safe-buffer instead of a real pointer array. The safe bet is to keep it only with the scan bit, I guess. I didn't think a lot if this organization of the information is the best for the GC implementator, but it's simple and opens the door to experimentation, so I think it's better to have a possibility even when is not the better solution than not having anything; the interface can be refined in the future. Since you are already playing with the compiler, do you think it's possible to change the compiler to provide this information? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #38 from Leandro Lucarella llu...@gmail.com 2010-07-22 19:26:36
PDT ---
If I'm understanding the patch right, I think I found a bug. At the end of
reallocNoSync():
+if (psize size || // if new size is bigger
+psize size * 2) // or less than half
+{
+p2 = mallocNoSync(size, bits, bitMask);
+
+psize -= bitMaskSize;
+size -= bitMaskSize;
Shouldn't size and psize be updated before mallocNoSync() is called? Otherwise
a block a word larger than needed would be allocated.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #31 from Leandro Lucarella llu...@gmail.com 2010-07-21 08:38:06 PDT --- (In reply to comment #30) Hm... I'd love to get this into D2, but the diffs are a bit large to apply by hand. I don't suppose you'd be inclined to provide a D2 patch as well? It should be pretty similar to the Tango patch. I would be nice to split the patch in smaller changes too, because there are a couple of extra optimizations not related to the precise scanning (for example, making findPool() use a binary search, I was just about to implement the same optimization in my GC :). There are a few changes of structure not related to the patch too, which improves the code, but makes harder to port the patch to other GCs. Thanks! -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #689 is|0 |1 obsolete|| --- Comment #32 from nfx...@gmail.com 2010-07-21 11:49:11 PDT --- Created an attachment (id=692) D1 - patch for dmd for creating pointer bitmasks - don't use the dmd provided bit array type anymore to make the patch more 64 bit friendly - slightly change PointerMap format -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #34 from nfx...@gmail.com 2010-07-21 11:57:02 PDT --- I don't really use D2 (all my code is in D1). Porting it to D2 will require dealing with the recently added array append stuff. Not sure how hard that would be, but currently I have no intention doing the port myself. Also note that the GC mark code is unoptimized. I'm not sure how much optimization potential there is, but my own attempts have been unsuccessful so far. About the 64 bit issue: to me it looked like dmd can never cross compile, and if you want to compile it as 64 bit app, it must generate 64 bit code. Or is that wrong? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #35 from Leandro Lucarella llu...@gmail.com 2010-07-21 11:59:40 PDT --- (In reply to comment #34) I don't really use D2 (all my code is in D1). Porting it to D2 will require dealing with the recently added array append stuff. Not sure how hard that would be, but currently I have no intention doing the port myself. Also note that the GC mark code is unoptimized. I'm not sure how much optimization potential there is, but my own attempts have been unsuccessful so far. About the 64 bit issue: to me it looked like dmd can never cross compile, and if you want to compile it as 64 bit app, it must generate 64 bit code. Or is that wrong? I don't know how it should finally be, but right now, even if you compile DMD as a 64 bits app, it generates 32 bits code (I didn't even find any options to make it generate 64 bits code :). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #36 from nfx...@gmail.com 2010-07-21 12:05:08 PDT --- I guess we will have to see how Walter's 64 bit port will look like. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #27 from Leandro Lucarella llu...@gmail.com 2010-07-20 19:33:05
PDT ---
I'm trying to test this patch but I'm having some problems compiling Tango (I'm
using 0.99.9, not trunk). With the patched DMD, I get this error:
dmd: mtype.c:5671: void PointerMap::pointer(size_t): Assertion `offset
m_size' failed.
Compiling the file: tango/util/digest/MerkleDamgard.d
Here is some output from a GDB session:
(gdb) bt
#0 0x2b421bf3c175 in *__GI_raise (sig=value optimized out) at
../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x2b421bf3ef80 in *__GI_abort () at abort.c:92
#2 0x2b421bf352b1 in *__GI___assert_fail (assertion=0x58be62 offset
m_size, file=value optimized out, line=5671, function=0x58bea0 void
PointerMap::pointer(size_t)) at assert.c:81
#3 0x004f5d55 in PointerMap::pointer (this=0x7fff15974fc0, offset=20)
at mtype.c:5671
#4 0x004eaf15 in TypeDArray::fillPointerMap (this=0x11735e0,
pm=0x7fff15974fc0, offset=12) at mtype.c:2241
#5 0x004679d4 in VarDeclaration::fillPointerMap (this=0x1130700,
pm=0x7fff15974fc0, a_offset=0) at declaration.c:1379
#6 0x0040488b in AttribDeclaration::fillPointerMap (this=0x11307c0,
pm=0x7fff15974fc0, offset=0) at attrib.c:289
#7 0x00542327 in ClassDeclaration::toObjFile (this=0x1130150,
multiobj=0) at toobj.c:484
#8 0x00404689 in AttribDeclaration::toObjFile (this=0x113afd0,
multiobj=0) at attrib.c:240
#9 0x004c0da1 in Module::genobjfile (this=0x112bfd0, multiobj=0) at
glue.c:267
#10 0x004e1560 in main (argc=13, argv=0x111f930) at mars.c:1285
(gdb) list
5666 * Actually does nothing if the offset isn't aligned.
5667 */
5668
5669void PointerMap::pointer(size_t offset)
5670{
5671assert(offset m_size);
5672//reject unaligned pointers
5673if (offset % sizeof(size_t))
5674return;
5675size_t bitpos = offset / sizeof(size_t);
(gdb) print offset
$1 = 20
(gdb) print m_size
$2 = 20
(gdb) up
#4 0x004eaf15 in TypeDArray::fillPointerMap (this=0x11735e0,
pm=0x7fff15974fc0, offset=12) at mtype.c:2241
2241pm-pointer(offset + sizeof(size_t));
(gdb) list
2236}
2237
2238void TypeDArray::fillPointerMap(PointerMap *pm, size_t offset)
2239{
2240// like struct Array { size_t length; byte* data; }
2241pm-pointer(offset + sizeof(size_t));
2242}
2243
2244/* TypeAArray
*/
2245
(gdb) print *pm
$3 = {
m_bits = {
Object = {
_vptr.Object = 0x5939d0
},
members of Bits:
bitdim = 3,
allocdim = 1,
data = 0x11e4c70
},
m_size = 20
}
(gdb) print offset
$4 = 12
I don't know enough about DMD internals to debug this myself, so any help will
be very much appreciated.
I'd like to run my test suite to the GC with precise scanning to see how it
goes. I've noticed that false pointers can add a lot of variance in the time a
program can take in Linux, where the addresses returned by mmap() is
randomized, so there are times where the address range returned by mmap() is
much more prone to receive false pointers. See this for the full story:
http://www.llucax.com.ar/blog/blog/post/-7a56a111
Running dil to generate the full Tango documentation can take from 50 to 80
seconds depending on the address range returned by the OS (I suspect because of
false pointers; which I hope to prove trying this patch :)
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #28 from Leandro Lucarella llu...@gmail.com 2010-07-20 19:51:19
PDT ---
Some extra info:
(gdb) up
#5 0x004679d4 in VarDeclaration::fillPointerMap (this=0x1130700,
pm=0x7fff15974fc0, a_offset=0) at declaration.c:1379
1379type-fillPointerMap(pm, offset + a_offset);
(gdb) list
1374
1375void VarDeclaration::fillPointerMap(PointerMap *pm, size_t a_offset)
1376{
1377//printf(VarDeclaration::fillPointerMap() %s, ty = %d, offs=%d\n,
toChars(), type-ty, (int)offset);
1378if (!isDataseg())
1379type-fillPointerMap(pm, offset + a_offset);
1380}
1381
1382/**
1383 * If a variable has an auto destructor call, return call for it.
I have commented out that printf() and this is what I got:
VarDeclaration::fillPointerMap() bytes, ty = 19, offs=8
VarDeclaration::fillPointerMap() buffer, ty = 0, offs=12
dmd: mtype.c:5671: void PointerMap::pointer(size_t): Assertion `offset
m_size' failed.
And this is the piece of D code triggering the assertion:
package class MerkleDamgard : Digest
{
private uintbytes;
private ubyte[] buffer; This one!
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #26 from nfx...@gmail.com 2010-07-18 14:20:24 PDT --- @Sean Kelly: you said something about different ways of storing the mask. Do you have any more concrete suggestions? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #25 from Leandro Lucarella llu...@gmail.com 2010-07-04 08:05:15 PDT --- (In reply to comment #23) I just voted for it. It would be great if you could define some benchmarks by which you assess the improvements your approach is bringing. I will try to do a couple of benchmarks when I have the time, but I think the DMD-part of the patch should be merged, even if the current GC is slower with the precise scanning, because having info on the pointers locations open a lot of new possibilities GC-wise, like moving collectors. This can be explored in the feature, once the compiler provide the necessary information about types to the GC. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #21 from Leandro Lucarella llu...@gmail.com 2010-07-02 05:41:22 PDT --- I care! But I guess that if I'm the only one you are wasting your time :) I'd suggest to bring it up in the DMD (or even druntime, but I guess that one is D2-only) devel list: http://lists.puremagic.com/mailman/listinfo/dmd-internals Other lists: http://lists.puremagic.com/mailman/listinfo -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Rob Jacques sandf...@jhu.edu changed: What|Removed |Added CC||sandf...@jhu.edu --- Comment #22 from Rob Jacques sandf...@jhu.edu 2010-07-02 07:00:20 PDT --- I also care. Keep up the good work :) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Andrei Alexandrescu and...@metalanguage.com changed: What|Removed |Added CC||and...@metalanguage.com --- Comment #23 from Andrei Alexandrescu and...@metalanguage.com 2010-07-02 09:40:25 PDT --- I just voted for it. It would be great if you could define some benchmarks by which you assess the improvements your approach is bringing. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #24 from David Simcha dsim...@yahoo.com 2010-07-02 18:29:07 PDT --- I'm thoroughly impressed. Now that someone wrote a better patch than I did, with some of the plumbing issues resolved, I wish I could just use all 10 votes on it. Then again, I've gotten to the point where I'm good at working around the conservativeness of the GC. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #13 from nfx...@gmail.com 2010-06-27 14:07:33 PDT --- Created an attachment (id=680) D1 - patch for dmd for creating pointer bitmasks -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #14 from nfx...@gmail.com 2010-06-27 14:08:34 PDT --- Created an attachment (id=681) D1 - patch for Tango's runtime to enable precise GC scanning -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #15 from nfx...@gmail.com 2010-06-27 14:21:58 PDT --- I posted two patches to enable precise GC heap scanning under D1/Tango. All user programs will make use of the precise scanning; no modifications required. The dmd patch makes dmd generate an additional field in TypeInfo_Struct and ClassInfo. These fields point to pointer bitmasks for the referenced type. The patch is written in such a way, that it won't break unpatched Tango or Phobos1 runtimes. In particular, this means the patched compiler should be useable with an unpatched Phobos1. (And I don't intend to write a Phobos1 patch. Phobos1 is ded.) The tango patch makes use of the generated bitmasks. It is based on dsimcha's patch. The mark phase and the bitmask format are completely different, but the brain-drilling changes to add bitmask pointers to the memory blocks are the same. This patch is also designed in such a way, that the patched runtime can be used with an unpatched compiler (in this case, it defaults to conservative scanning). The patch also contains a test program (pm.d) for the compiler generated bitmasks. The patch should be able to handle all D types. The internal nodes for associative arrays are still scanned conservatively. You would have to dynamically allocate and fill pointer maps for each AA, and I'll just say: sorry, but no. Note that the bitmask format is different compared to dsimcha's patch. Now it's a bitmap, where each bit represents an aligned, pointer sized chunk of memory. Also, I don't use templated TypeInfos as dsimcha was suggesting. I'm convinced this approach would slow down compile times and generate masses of bloat. It also would be hard to implement. The question what the TypeInfo of a TypeInfo template instance should be was unsolved, too. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added Attachment #680 is|0 |1 obsolete|| --- Comment #16 from nfx...@gmail.com 2010-06-27 14:36:30 PDT --- Created an attachment (id=682) D1 - patch for dmd for creating pointer bitmasks (forgot some minor stuff - also, this patch is loosely against dmd 1.062; Walter forgot to tag the 1.062 release in svn) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463
--- Comment #17 from nfx...@gmail.com 2010-06-27 14:49:50 PDT ---
PS: I forgot to handle TypeInfo_Typedef. Apply this change in object_.d:
@@ -370,6 +370,7 @@ class TypeInfo_Typedef : TypeInfo
override TypeInfo next() { return base; }
override uint flags() { return base.flags(); }
+override PointerMap pointermap() { return base.pointermap(); }
override void[] init() { return m_init.length ? m_init : base.init(); }
TypeInfo base;
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #12 from Sean Kelly s...@invisibleduck.org 2010-06-08 12:22:20 PDT --- Yeah, the patch doesn't work any more. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 nfx...@gmail.com changed: What|Removed |Added CC||nfx...@gmail.com --- Comment #11 from nfx...@gmail.com 2010-05-06 04:28:59 PDT --- What is the status of this? Also, did the newest changes in the runtime (for array appending) trash this patch? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #7 from Sean Kelly s...@invisibleduck.org 2009-11-03 07:52:44 PST --- Nice work! It may be preferable to store the pointer elsewhere however. I believe all blocks returned by the allocator must be 16 byte-aligned, so tacking a pointer onto the end of a block either screws this up or uses up a lot more space than necessary. I also kind of wish that the pointer didn't have to be stored at all for small block sizes, since simply storing the mask itself would take up less space (admittedly, at the expense of more complicated logic). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #8 from David Simcha dsim...@yahoo.com 2009-11-03 08:06:43 PST --- (In reply to comment #7) Nice work! It may be preferable to store the pointer elsewhere however. I believe all blocks returned by the allocator must be 16 byte-aligned, so tacking a pointer onto the end of a block either screws this up or uses up a lot more space than necessary. I don't understand. If someone requests, for example, a 12-byte allocation, the pointer is stored in the last 4 bytes (on 32-bit) of a 16-byte block. I don't increase the block capacity unless I have to. Yes, occasionally it will result in a doubling of the required capacity, but unless you request an allocation within 4 bytes of a full block size, it uses no extra space. The expected value under pseudo-random allocation sizes is probably (I haven't worked this out formally) only 4 bytes on 32-bit. Furthermore, if the NO_SCAN bit is set, no bit mask information at all is stored. This optimization was part of the reason I chose to use the end of the block: Otherwise I probably would have had to reserve space somewhere else before I knew the status of the NO_SCAN bit, meaning that this optimization would have been unimplementable. I also kind of wish that the pointer didn't have to be stored at all for small block sizes, since simply storing the mask itself would take up less space (admittedly, at the expense of more complicated logic). I thought about this, but the problem I kept coming up with was that tracking the size of the mask would require a couple bytes anyhow. IMHO it was important to keep this patch relatively simple and stupid and easy to debug. It's clearly not a long-term solution to our GC woes because it leaves unaddressed so many unrelated issues that will eventually require a full redesign. It's more of an incremental improvement to make the GC good enough until D is popular enough that some GC expert implements generational, moving, parallel, etc. GC. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Sean Kelly s...@invisibleduck.org changed: What|Removed |Added Status|NEW |ASSIGNED --- Comment #9 from Sean Kelly s...@invisibleduck.org 2009-11-03 08:15:26 PST --- My apologies. Those comments were based on your description of what you were doing, and I came to the wrong conclusion. I'll give the patch a try! I'm also kind of curious what impact this will have on collection times. Seems like it should be faster overall. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #1 from David Simcha dsim...@yahoo.com 2009-11-01 10:46:03 PST --- Created an attachment (id=488) Templates to generate bit masks, documentation of format. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 David Simcha dsim...@yahoo.com changed: What|Removed |Added Attachment #487 is|0 |1 obsolete|| --- Comment #2 from David Simcha dsim...@yahoo.com 2009-11-01 10:48:54 PST --- Created an attachment (id=489) Correct patch. Accidentally attached the wrong one. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 Leandro Lucarella llu...@gmail.com changed: What|Removed |Added CC||llu...@gmail.com --- Comment #3 from Leandro Lucarella llu...@gmail.com 2009-11-01 11:38:16 PST --- The patch looks nice. I have some questions: * Why did you choose to store the bitmask after the SENTINEL_POST and not before? I think that storing the bitmask before the SENTINEL could let you detect a corrupted bitmaks when version SENTINEL is compiled. * In the bitMaskMixin string mixin you have a nested function setBitMask() that's used only once. I wonder if you reused that function before or if you put that code in a nested function just because you you think it's more clear that way. It kind of confused me at first. * Why is the bitMaskMixin a mixin and not just a plain function? I can't see any reason to make it a string mixin, I am missing something? I find this very confusing and makes the code harder to follow, since some variables appear from nowhere. Thanks for the good work. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #4 from David Simcha dsim...@yahoo.com 2009-11-01 11:49:58 PST --- 1. I chose to store the bitmask after SENTINEL_POST so that none of the assumptions of the sentinel code (such as that the sentinel is immediately after the data) changes. 2. The fact that setBitMask() is a nested function is a minor holdover from when the design was a little different. If anyone really hates it a lot, it can be refactored. 3. The mixin is because I needed a lot of the same logic in realloc() and extend() and it was complicated enough that I felt it was the lesser of two evils to use a mixin, even with the variables appearing out of nowhere magic, rather than duplicate that logic. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #5 from Leandro Lucarella llu...@gmail.com 2009-11-01 12:31:57 PST --- (In reply to comment #4) 1. I chose to store the bitmask after SENTINEL_POST so that none of the assumptions of the sentinel code (such as that the sentinel is immediately after the data) changes. Seems reasonable, the SENTINEL version is not very used anyway. 2. The fact that setBitMask() is a nested function is a minor holdover from when the design was a little different. If anyone really hates it a lot, it can be refactored. I agree is not terrible, but since it's a pretty trivial change I guess it could be nice to remove it, to improve readability (I don't think is a performance problem, readability and complexity is my only concern). If you don't feel like changing it yourself I can upload an amended patch. 3. The mixin is because I needed a lot of the same logic in realloc() and extend() and it was complicated enough that I felt it was the lesser of two evils to use a mixin, even with the variables appearing out of nowhere magic, rather than duplicate that logic. Sure, duplicating code is never a good idea. The question is, why it can't be done with a plain-old function? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 3463] Integrate Precise Heap Scanning Into the GC
http://d.puremagic.com/issues/show_bug.cgi?id=3463 --- Comment #6 from David Simcha dsim...@yahoo.com 2009-11-01 12:36:22 PST --- 3. The mixin is because I needed a lot of the same logic in realloc() and extend() and it was complicated enough that I felt it was the lesser of two evils to use a mixin, even with the variables appearing out of nowhere magic, rather than duplicate that logic. Sure, duplicating code is never a good idea. The question is, why it can't be done with a plain-old function? Because I needed to dump a whole bunch of variables (not just 1) into the stack frames of realloc() and extend() and the only way this could have been done with a plain old function would be to create a struct, create a function that returns the struct, etc. or to use lots and lots of out paramters. I really felt the mixin was the least unclear way that this logic could be injected into both extend() and realloc(). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
