| 00:01:58 | * | dedis15 quit (K-Lined) |
| 00:03:19 | dom96 | This dedis seemed like some sort of weird bot attack. |
| 00:04:00 | Araq | nah, he is just a guy who loves nimrod |
| 00:04:07 | Araq | and who can blame him? :P |
| 00:04:16 | dom96 | And joins every channel to tell everyone about it right? |
| 00:04:30 | Araq | right |
| 00:04:52 | fowl | he ws in 3 channels im on |
| 00:05:13 | dom96 | There were like a lot of different versions of him |
| 00:05:25 | fowl | ah yeah |
| 00:05:27 | dom96 | dedis, dedis19, dedis15, i'm guessing dedis1-20+ |
| 00:05:32 | fowl | i didnt notice that at first |
| 00:05:41 | dom96 | It was an alien invasion :D |
| 00:38:22 | fowl | dom96: https://gist.github.com/4116737 :) |
| 01:06:56 | * | Nimrod quit (Ping timeout: 255 seconds) |
| 01:11:49 | * | Nimrod joined #nimrod |
| 01:39:18 | zahary | Araq, still here? |
| 01:47:38 | fowl | hrm i have some problems with const >:/ |
| 01:48:11 | zahary | Araq has left probably, maybe I can help? |
| 01:50:45 | zahary | Araq: I traced the leak to a single TNode.sons sequence marked conservatively from the stack. I'm too tired and I'll be going to bed now. In the meanwhile, please tell me how to fetch the sequence size from the PCell address |
| 01:53:45 | fowl | zahary: sf::Text::getFont() returns const Font*, but i'm unable to use this because nimrod forward-declares all variables (i suspect this should be turned off for cpp generation) |
| 01:56:16 | fowl | nimrod declares it as sf::Font* varname; i tried doing type CPFont* {.importc: "const sf::Font*".} = ptr TFont |
| 01:58:24 | zahary | and the CPFont* trick didn't work? |
| 01:59:15 | zahary | I've had similar problems before actually. Nimrod tries hard to cast types, but the C++ rules doesn't allow some of the casts |
| 01:59:47 | fowl | no it still is declared as sf::Font* |
| 02:00:45 | zahary | do you happen to have another ptr TFont type? try to remove it temporary |
| 02:01:26 | zahary | e.g. if you also have PFont* {.importc: "sf::Font*".} |
| 02:02:20 | fowl | nope i only have TFont |
| 02:05:51 | * | Nimrod quit (Ping timeout: 245 seconds) |
| 02:06:23 | zahary | ahm, so the compiler ignores the importc pragma on the ptr type and just uses what is given for the pointed-to type |
| 02:06:46 | fowl | yea |
| 02:07:28 | fowl | and i think if it didnt do forward-declarations in c++ it would be easier to support constructors |
| 02:07:33 | zahary | if you change TFont* to something like {.importc: "sf::TEST".} will CPFont become sf::TEST* |
| 02:07:51 | zahary | … just to make sure this is the problem |
| 02:08:29 | fowl | yep |
| 02:10:37 | zahary | we could fix the importc problem, but ideally we should understand a bit more about C++'s const types |
| 02:11:42 | zahary | you probably can now make a type like CFont that is importc: "const sf::Font" and then use prt CFont |
| 02:14:45 | fowl | that seems to work |
| 02:16:04 | * | Nimrod joined #nimrod |
| 02:18:18 | fowl | but to make it compatible with TFont stuff i'd probably have to call TFont instead sfFont then have type TFont = sfFont | cFont |
| 02:18:39 | fowl | bbl, dinner |
| 04:35:33 | * | XAMPP quit (Quit: Leaving) |
| 06:40:43 | reactormonk | Araq, what do you think of the idea of the special argument syntax in scala that allows you to mark arguments that should be evaluated lazyly? Or does nimrod cover that with templates/macros? |
| 07:42:30 | * | Nimrod left #nimrod ("["Textual IRC Client: www.textualapp.com"]") |
| 08:52:16 | * | Araq_ joined #nimrod |
| 09:51:46 | * | Araq_ quit (Read error: Connection timed out) |
| 09:52:33 | * | Araq_ joined #nimrod |
| 10:13:38 | * | Araq_ quit (Read error: Connection timed out) |
| 10:15:33 | * | Araq_ joined #nimrod |
| 11:15:14 | * | Araq_ quit (Read error: Connection timed out) |
| 11:17:33 | * | Araq_ joined #nimrod |
| 12:15:08 | * | Araq_ quit (Quit: ChatZilla 0.9.89 [Firefox 16.0.2/20121024073032]) |
| 12:51:07 | zahary | Araq, your marker procs are wrong. They don't do the equivalent of forAllChildren. instead they treat all objects as leafs and directly go to doOperation |
| 12:51:17 | * | apriori| joined #nimrod |
| 12:53:24 | apriori| | guys.. say I have a given basetype A, and a type B which inherits from A - actually every visible member of A should be visible to an instance of var B or do I need to cast down to A? |
| 12:54:12 | apriori| | ah, forget it.. stupid error by me |
| 12:55:35 | zahary | the previous message should read * Araq, your marker procs are wrong? * |
| 12:56:43 | apriori| | btw., is there a public import? |
| 12:57:08 | apriori| | like.. say import something in a module, and I want to forward the import to the module importing my module |
| 12:57:36 | apriori| | or must I use "include" then? (which I wouldnt like, because isnt that like C #include?) |
| 12:58:34 | zahary | not yet, but we've talked about it |
| 12:58:57 | zahary | there will be export keyword, so you'll be able to say import foo; export foo |
| 12:59:08 | apriori| | hm |
| 12:59:29 | apriori| | wih export being able to name the entire module? |
| 13:01:02 | apriori| | btw., another thing I constantly don't quite like is the special syntax of importing by pathspec like import "subpath/module" |
| 13:01:19 | apriori| | vs something like import subpath/module or import subpath.module |
| 13:01:30 | zahary | let's say you do this from your module bar. the code that imports bar will see bar.foo as module, so bar.foo.someProc will be the syntax to call it |
| 13:01:30 | zahary | probably, there will also be a way to flatten the exports (pretend that they are coming from your own module) |
| 13:02:20 | apriori| | yeah, ok |
| 13:03:02 | zahary | I have asked about import subpath.module before and Araq gave me some reason why it's problematic, but can't remember the details |
| 13:03:21 | apriori| | I dont even need that dot... |
| 13:03:29 | apriori| | but one should really get rid of having to use a string literal |
| 13:04:02 | zahary | the string literal gives you spaces in the name (if you are crazy enough to use them) |
| 13:04:18 | apriori| | one should instantly shot those anyway :P |
| 13:04:38 | apriori| | well, that may be true... |
| 13:04:51 | apriori| | buts its inconsistent with normal import in current path |
| 13:06:06 | * | q66 joined #nimrod |
| 13:09:57 | apriori| | ohm, what is the bitwise NOT operator in nimrod? |
| 13:11:59 | apriori| | k, the tutorial says, its apparently also NOT |
| 14:41:42 | * | apriori| quit (Ping timeout: 244 seconds) |
| 14:47:39 | * | FreeArtMan joined #nimrod |
| 16:10:24 | dom96 | fowl: yay. Nice job! |
| 16:10:59 | dom96 | elif defined(MacOS): ## is this the right conditional? |
| 16:11:22 | dom96 | IIRC it's darwin |
| 16:33:59 | * | XAMPP joined #nimrod |
| 16:33:59 | * | XAMPP quit (Changing host) |
| 16:33:59 | * | XAMPP joined #nimrod |
| 17:21:05 | * | FreeArtMan quit (Quit: Out of this 3D) |
| 17:37:16 | Araq | reactormonk: lazy parameters turned out to be problematic in D but I can't remember the details |
| 17:37:25 | Araq | but yeah, nimrod's way is to use a macro instead |
| 17:40:11 | Araq | zahary: it's unlikely they're wrong, we have tests guarding against that ... and in fact they had a bug that adrianv encountered |
| 17:48:27 | zahary | please explain how the CollectCycles is supposed to work |
| 17:49:22 | zahary | http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf is it supposed to implement the algorithm from here? |
| 17:50:38 | zahary | they are wrong in the sense that they don't traverse the whole graph when decrementing the references. I'm sure they don't do that as I stepped through the code, but maybe your algorithm is not supposed to do it? |
| 17:51:58 | Araq | the paper was the base for the GC, yes but the cycle collector works differently |
| 17:53:38 | zahary | so what is supposed to happen? can you explain it in a few sensences? |
| 17:54:12 | Araq | it's called "Christoper's partial mark-sweep garbage collector" |
| 17:54:22 | Araq | Python uses the same algorithm |
| 17:54:40 | Araq | the idea is to traverse the graph and decref reference counts |
| 17:55:35 | Araq | afterwards the objects with RC == 0 are "dead" |
| 17:55:55 | zahary | so far it's like the above paper |
| 17:56:06 | Araq | meaning they are not referenced by some extern root |
| 17:56:17 | zahary | traverse the whole graph, right? |
| 17:56:44 | Araq | the transitive closure of the potential roots of a cycle |
| 17:56:51 | Araq | not the whole graph |
| 17:57:02 | zahary | yes, the whole graph from a given root is what I meant |
| 17:57:06 | Araq | so yeah it works quite like the paper but it's not incremental |
| 17:57:18 | Araq | I use no colors |
| 17:57:26 | zahary | how do you known that I have traversed some node alraedy? you don;t use any coloring? |
| 17:58:04 | zahary | i.e. what prevents endless recursion on cycle |
| 18:00:33 | Araq | in collectCycles the first loop is not recursive |
| 18:00:44 | Araq | so no endless recursion is possible |
| 18:01:15 | zahary | but then it doesn't recref the "transitive closure of the potential roots of a cycle"? |
| 18:01:20 | * | TheVoid quit (Read error: Connection reset by peer) |
| 18:01:50 | Araq | hrm true |
| 18:02:08 | Araq | well the second loop uses a var marker: TCellSet |
| 18:03:14 | zahary | but the second loop just adds references, in effect it will add more to the refcount than what was taken in the first step |
| 18:03:44 | zahary | but even if it wasn't doing this, the first step will be not enough |
| 18:04:19 | Araq | dunno my head is hurting today anyway |
| 18:04:37 | zahary | next question. why do you add a cycleCandidate in incRef? |
| 18:04:51 | zahary | you are supposed to remove a previous candidate there |
| 18:04:58 | Araq | however I am sure it's not as simple as you think it is :P |
| 18:05:26 | Araq | after all we have tests for this ... |
| 18:05:47 | Araq | with some evil cycles |
| 18:05:50 | zahary | I can try to produce some leak test cases armed with the new knowledge |
| 18:06:16 | Araq | yeah good |
| 18:06:44 | Araq | for instance what you need to understand is that 'forallChildren' is not recursive in the way you think it is |
| 18:07:06 | zahary | yeah, ok, I got that now, you use externally driven recursion as in the second loop |
| 18:07:13 | Araq | it only traverses the *direct* embedded children |
| 18:07:27 | Araq | the recursion is only there for array of array of object etc. |
| 18:07:39 | Araq | tyRef, tySeq, tyString are always leaves |
| 18:08:10 | zahary | what about my incRef question? |
| 18:08:33 | zahary | also, I've read the papers and there are some other issues raised there that I haven't looked up in the code yet |
| 18:08:58 | zahary | do you consider objects from the ZCT that survived collection as a cycle candidates for the next collection? |
| 18:09:52 | Araq | I can't remember but pointers in the ZCT can't be part of a cycle |
| 18:10:06 | Araq | you can't build cycles with only pointers on the stack |
| 18:10:50 | zahary | you can orphan a cycle by "cutting" the only refence to it from the stack, thus skipping the write barrier |
| 18:11:09 | Araq | yeah that's a but in the original paper |
| 18:11:29 | Araq | but I do add to the cycle candidates in incRef for this reason |
| 18:11:35 | Araq | *that's a bug |
| 18:11:51 | zahary | that's what I though too |
| 18:12:22 | zahary | there is also a more recent and a bit more complicated paper that uses a more efficient write barrier |
| 18:12:39 | Araq | "more efficient"? |
| 18:12:42 | zahary | it adds fewer objects as cycle candidates |
| 18:12:57 | Araq | the original paper adds to some external heap local arrays |
| 18:12:58 | zahary | also, it can be extended to concurrent operation |
| 18:13:23 | Araq | that's so bad for performance that I dunno if they really ever implemented that ... |
| 18:13:47 | Araq | I mean the original write barrier completely destroys performance |
| 18:13:58 | Araq | been there, done that :P |
| 18:14:32 | zahary | most of the papers use this local buffers, but in a different way |
| 18:14:49 | zahary | do you remember what did you implemented? |
| 18:15:55 | Araq | (I meant thread local arrays) |
| 18:16:15 | zahary | yeah, sure |
| 18:16:37 | Araq | well I did quite a lot with arrays, tried lots of things |
| 18:17:01 | Araq | you can also use some crazy stuff with bitsets and intersections |
| 18:17:30 | Araq | for instance you can use a negative RC to index into the ZCT for fast ZCT removal |
| 18:18:10 | zahary | do you remember marking pointers with a dirty bit and adding only the first "dirtifying" write as a candidate? this is one of the suggested techniques |
| 18:19:02 | Araq | hu? potential cycles are already kept in a bitset ... no duplicates in there anyway |
| 18:19:26 | zahary | it's a hash table to be precise |
| 18:19:51 | zahary | and you'll have to scan the candidate on the next CollectCycles |
| 18:19:57 | Araq | it's a hash table of bitsets |
| 18:20:04 | zahary | so it's a win if you avoid adding candidates |
| 18:20:44 | Araq | I fight that with static type analysis |
| 18:20:56 | zahary | well, sure. everybody does that |
| 18:21:14 | Araq | yeah but I can cheat with 'acyclic' :P |
| 18:21:38 | zahary | all of this is orthogonal to the specific write barrier |
| 18:22:47 | Araq | all of this is also largely irrelevant for hunting the memory leak ;-) |
| 18:23:51 | Araq | unless you fear the fix will slow doewn the GC tremendously :D |
| 18:24:43 | Araq | btw the compiler/GC system tries hard to avoid *adding* to the ZCT |
| 18:24:59 | Araq | because that's what's much more expensive |
| 18:25:20 | zahary | fixing CollectCycles may slow things down a little bit, but I don't worry about this now. I'm just building an inventory of what future improvements are possible |
| 18:25:37 | Araq | addNewObjToZCT for instance makes benchmarks worse but the compiler itself faster ... |
| 18:25:52 | zahary | btw, did you catch my previous message about the seq marked from the stack |
| 18:26:01 | zahary | now that's a bitch :/ |
| 18:26:06 | Araq | I did but thought you changed your mind |
| 18:26:16 | Araq | and now blame the cycle collector |
| 18:26:23 | zahary | nope, I just disabled temporary stack marking to arrive at the next problem |
| 18:26:34 | dom96 | Araq: Well, i've analysed the builder with the thread analyser (now that you've fixed that bug), and it doesn't seem to be coming up with anything. |
| 18:26:43 | Araq | dom96: I know |
| 18:26:51 | dom96 | Araq: I get those "analysis could not be complete" warnings though |
| 18:27:01 | Araq | yeah but they are irrelevant |
| 18:27:16 | Araq | I will analyse your code but not today |
| 18:28:06 | Araq | can you try to disable threads and see if the problem is still there? |
| 18:28:43 | Araq | zahary: is it an interior pointer? or some other false positive? |
| 18:30:53 | dom96 | Araq: unfortunately no |
| 18:31:13 | Araq | zahary: think about it ... both PNode and PRope are potentially cyclic in Java ... the 'acyclic' pragma is quite important ;-) |
| 18:32:26 | zahary | the acyclic pragma is super cool, but static "is cyclic" is just one aspect present in all algorithms |
| 18:34:14 | zahary | I use the following code to print some info about the sequence: |
| 18:34:14 | zahary | let sq = cast[PGenericSeq](cellToUsr(objStart)) |
| 18:34:14 | zahary | c_fprintf(c_stdout, "seq len: %d\noffset: %d\n", sq.len, cast[TAddress](p) - cast[TAddress](sq)) |
| 18:34:23 | zahary | I get seq len: 1 and offset: 24 |
| 18:35:01 | Araq | use '%ld' instead |
| 18:35:09 | zahary | p is the original gcMark address |
| 18:36:22 | zahary | from the leakDetector code, I previously determined that this is a sequence allocated in ast.nim/shallowCopy (the sons on the last line) |
| 18:38:57 | Araq | well looks like a false interior pointer |
| 18:40:01 | Araq | we have a way to turn them off |
| 18:40:30 | Araq | but it requires a GCC extension (the "guard" thing) and slows down everything |
| 18:41:29 | zahary | it's also not the complete problem. I've just added a bool flag in system.nim that disables stack marking and I set it just before my fullcollect |
| 18:41:54 | Araq | sounds dangerous :D |
| 18:42:27 | zahary | could trigger more collections, but not fewer :) |
| 18:46:31 | Araq | so ... I guess the leak is gone with boehm's gc? |
| 18:48:05 | zahary | nope, but I cannot disable the stack marking there |
| 18:50:10 | Araq | yay :-) |
| 18:54:58 | Araq | have you tried --gc:boehm and -d:release btw? |
| 18:55:22 | zahary | probably not |
| 18:55:32 | Araq | often debug builds are much worse wrt false positives on the stack as a release build makes much more efficient use of the stack |
| 18:59:47 | * | Vladar joined #nimrod |
| 18:59:50 | Vladar | Hi |
| 19:05:09 | Araq | hi Vladar |
| 19:07:51 | * | ekselkiu joined #nimrod |
| 19:16:09 | Araq | see you later |
| 20:01:18 | zahary | Araq, I pushed 2 leak cases. one is due to the bug in CollectCycles. the other is about orphaning a cycle from the stack (the common issue from the paper I mentioned) |
| 20:14:41 | Araq | damn you, zahary |
| 20:15:18 | Araq | meh this means I have to read and understand my GC again ... |
| 20:15:45 | Araq | can't there ever be a release without hard bugs? |
| 20:19:03 | Araq | can't see how my algorithm fails for stackrefleak ... |
| 20:21:58 | Araq | oh I see :P |
| 20:22:10 | Araq | it's due to some optimization of mine I think |
| 20:24:50 | Araq | so yeah the shallow decref is wrong with the newObjRC1 optimization I think |
| 21:58:44 | zahary | I don't see how a shallow decref could work in any setting, you really need to walk the full graph there |
| 21:59:36 | zahary | about stackref: you can orphan a cycle by "cutting" the only refence to it from the stack, thus skipping the write barrier |
| 22:00:14 | zahary | the paper I read about it is this one: |
| 22:00:14 | zahary | http://researcher.watson.ibm.com/researcher/files/us-bacon/Paz05Efficient.pdf |
| 22:01:22 | zahary | I like it terse descriptions, but it also quotes very often the previous more detailed paper written partly by the same team: |
| 22:01:22 | zahary | http://www.cs.technion.ac.il/~erez/Papers/refcount.pdf |
| 22:01:33 | zahary | * its terse * |
| 22:04:25 | Araq | well I changed stackrefleak somewhat to prevent the generation of newobjrc1 but the leak remains |
| 22:05:01 | Araq | dunno what you mean but "cutting" the only reference to it from the stack ... |
| 22:05:15 | Araq | oh I see ... |
| 22:05:33 | Araq | XD |
| 22:06:31 | Araq | however I still think the shallow decref is correct if every node involved in the cycle is in 'cycleRoots' |
| 22:06:56 | Araq | which is what I thought to be the case given that it's added in incRef |
| 22:09:05 | zahary | it will be in cycleRoots only until the next collection, if it survives it all bets are off |
| 22:10:08 | Araq | yeah I noticed |
| 22:10:13 | Araq | that's the real bug |
| 22:10:16 | * | shevy joined #nimrod |
| 22:11:19 | Araq | otherwise the shallow decref would be correct, right? |
| 22:12:31 | zahary | well, if everything is kept in cycleRoots all the time what's the point of having such a collection? |
| 22:12:45 | zahary | you need to keep all objects that are part of the cycle in order to be correct |
| 22:14:16 | Araq | I still like the idea :P |
| 22:15:04 | zahary | the algorithm in the second paper sounds quite smart btw, I think you read a previous paper that really sounds ludicrous in the way it implements concurrent updates to the refcounts |
| 22:15:56 | Araq | I'm skimming the Paz05Efficient.pdf |
| 22:16:17 | zahary | yes, that's what I meant by second - in chronology |
| 22:20:37 | zahary | https://docs.google.com/viewer?a=v&q=cache:O0YPLKDnaVUJ:www.cs.technion.ac.il/~erez/presentations/cycle-collection.ppt+&hl=en&gl=bg&pid=bl&srcid=ADGEEShiepZGoyF0aUFkKEq-EXjYj54J7tnULa0lKZPFqHQOAewklEg1Us9EGMiOSa9VWk1mNA2Lq4qsnpK74xkH1Hmy9s9kgF0gIepR95g9pz5xu-e6g-x5ryMmo31WUQcgQK1KsM1F&sig=AHIEtbT413HA0crdzLzFgmn96f06MuEaTA |
| 22:20:48 | zahary | this is alternative presentation for the same paper |
| 22:21:30 | fowl | dom96: thanks |
| 22:22:35 | Araq | yay slides |
| 22:23:08 | Araq | well the idea is that you can ignore that cycle candidates that have been proven alive |
| 22:23:29 | Araq | until the write barrier indicates some changing of this subgraph again |
| 22:23:36 | Araq | in which case they are added again |
| 22:23:42 | zahary | all of them? |
| 22:23:48 | zahary | in the write barrier? |
| 22:23:49 | Araq | lol no |
| 22:23:58 | Araq | but a single root is enough |
| 22:24:08 | Araq | ok not with my totally broken shallow decref ... |
| 22:24:12 | Araq | but you get the idea |
| 22:24:33 | zahary | well, sure, don't do shallow decref and everything is fine |
| 22:24:59 | zahary | the papers go to great lengths to not put objects in the cycle roots unless it's really necessary |
| 22:25:35 | Araq | problem is: not everything is fine at all |
| 22:25:52 | Araq | because indeed the stack can keep the cycle alive |
| 22:26:03 | Araq | but hrm |
| 22:26:06 | Araq | maybe it can't |
| 22:26:16 | Araq | after all, we decref stack roots at the end again |
| 22:26:44 | zahary | it's explained in the 05 paz paper. if an object survives collection only because of a stack ref, it must be added to cycle roots for the next collection |
| 22:27:06 | Araq | true |
| 22:30:50 | Araq | btw I never got the optimization to prevent the "2n RC operations" |
| 22:33:01 | Araq | how can these prevented at runtime in practice? |
| 22:33:15 | Araq | all the workarounds are easily more expensive than the RC updates ... |
| 22:33:38 | Araq | and I can't think of a single workaround that would be cheaper ... |
| 22:36:28 | zahary | I haven't yet made it to the section where this is explained, but there are 2 components to the algorithm |
| 22:36:28 | zahary | one is the actual guarantees that it's enough to only add the "dirtifying change" (no more book keeping required) - you fix that with some special considerations when it's time to release the objects. the other bits are about concurrent operation and they could be argued as too expensive |
| 22:38:43 | Araq | it's academic anyway I think: the RCs are not updated for the example as it's either a stack location that traverses through the list or it's some swap() operation which can easily optimized away statically |
| 22:39:16 | Araq | (Nimrod's swap optimizes RC updates away too ...) |
| 22:40:46 | zahary | doesn't sound that academic to me. I can imagine a field to change a few times between collections. it's not only about swap |
| 22:41:07 | zahary | and if you lose nothing, how can you argue against it? |
| 22:42:35 | Araq | the example is a single pointer 'p' that changes its value in "a row" |
| 22:42:57 | Araq | if other pointer operations happen in between it's even harder to optimize the RC ops away |
| 22:43:25 | zahary | this is not the static lifetime analysis of RC updates of stack values |
| 22:43:38 | Araq | I know |
| 22:43:39 | zahary | I remember that paper, but this is different. |
| 22:43:48 | Araq | yes, it is different |
| 22:44:03 | Araq | can't see it ever work well in practice :P |
| 22:44:06 | zahary | you keep references counts normally, the only difference is what you decide to consider a cycle root for the next collection |
| 22:44:26 | Araq | what? |
| 22:44:38 | Araq | I don't think we're talking about the same topic then ... |
| 22:44:46 | zahary | well, read the paper |
| 22:46:01 | zahary | I haven't finished it yet. probably tomorrow I'll be able to make more precise statements about it :) |
| 22:47:21 | Araq | so ... are you up to fixing the cycle collector? |
| 22:47:30 | Araq | or should I do it? |
| 22:48:14 | zahary | I could try, but would like me changing a lot of stuff around there? I would store colors in the nodes instead of the aux hash tables, etc |
| 22:48:39 | Araq | why? |
| 22:49:50 | zahary | hash tables are quite slower in practice than direct memory acesses |
| 22:50:02 | zahary | … in my experience. |
| 22:50:18 | Araq | well the code already provides the colors |
| 22:50:20 | Araq | so fine |
| 22:50:38 | zahary | aux table could reduce memory usage. that's my only doubt |
| 22:50:52 | zahary | but only if you decide to compress the refcount as well |
| 22:51:02 | Araq | I'm not following |
| 22:51:15 | Araq | you got the lowest 3 bits in the RC for the colors |
| 22:51:23 | Araq | it's already there |
| 22:51:54 | zahary | they postulate that most objects have a ref count of 1, so they store a compressed refcount in a external bitmap. if it overflows, they allocate a full refcount in aux hash table |
| 22:52:15 | zahary | but I prefer inline count and colors until proven wrong :) |
| 22:52:33 | Araq | exactly :-) |
| 22:52:37 | zahary | that's from a previous paper btw, not the 05 one |
| 22:52:55 | Araq | aux hash table for RC looks very stupid |
| 22:53:20 | Araq | and we have no bit to spare anyway |
| 22:53:28 | zahary | got me thinking that certain objects are not sharable |
| 22:53:43 | zahary | maybe that's what they missed - a seq and string can't have ref count different from 1 |
| 22:53:51 | Araq | we could use the lowest bit of the type field |
| 22:54:04 | Araq | but then you need to clear that bit for accessing the type field |
| 22:54:07 | zahary | and you can have some special treatment for non sharable objects |
| 22:54:51 | Araq | but easier sharing is a feature of a GC'ed language |
| 22:55:00 | Araq | people make more and more use of sharing |
| 22:55:44 | Araq | you could instead go with per type blocks and have the type field only stored block-wise |
| 22:56:00 | Araq | and you save 8 bytes for every allocated object this way on a 64bit machine |
| 22:56:13 | zahary | yeah, I've thought about this. we really want ref string to have the same physical representation as a normal string - i.e. a direct pointer to allocated memory. the only difference is that it's sharable and default constructed to null |
| 22:56:39 | zahary | (that about sharing) |
| 22:57:02 | Araq | I have other plans instead of ref string ;-) |
| 22:57:08 | zahary | what are they? |
| 22:57:45 | Araq | PRope = object[le, ri: PRope, payload: array[0.., char]] |
| 22:58:04 | Araq | unsafeNew(myrope, sizeof(...)) |
| 22:58:43 | Araq | the old "extensible" struct hack of C |
| 22:59:26 | zahary | ok, but that's an alternative type to ref string. does your idea about "ref string" differ somehow from what I said? |
| 22:59:40 | zahary | * about "ref string" itself * |
| 22:59:49 | Araq | ref string would be inconsistent |
| 22:59:59 | fowl | i thought strings were already refs |
| 23:00:08 | zahary | under the hood |
| 23:00:17 | zahary | they have value semantics otherwise |
| 23:00:29 | zahary | when you said ref1 = ref2, now both refs point to the same objects |
| 23:00:32 | Araq | but you can do: PRefString {.shallow.} = object s: string |
| 23:00:35 | zahary | with strings you get copies |
| 23:00:41 | Araq | hrm, damn still one indirection left |
| 23:01:10 | zahary | what I said is that the compiler cheats a little bit and uses the same physical representation |
| 23:01:25 | Araq | well you can't have everything |
| 23:01:27 | zahary | changes the "porcelain" semantics of the types only |
| 23:01:37 | zahary | surely it can be implemented |
| 23:01:42 | Araq | either you go with destructors and value semantics |
| 23:02:06 | zahary | string - value semantics |
| 23:02:06 | zahary | ref string - ref semantics, but the same pointer to buffer implementation |
| 23:02:15 | zahary | what's wrong with that? |
| 23:02:20 | Araq | it can't work |
| 23:02:24 | zahary | why so? |
| 23:02:28 | Araq | and would special case 'ref string' in the language |
| 23:02:36 | Araq | think of buffer growing |
| 23:03:06 | Araq | I think the extensible struct C hack is all that's needed |
| 23:03:26 | Araq | and then you can have GC'ed immutable strings with O(1) concatenation |
| 23:03:41 | Araq | can't think why I even want 'ref string' then |
| 23:04:52 | zahary | ahm, your point is that if the buffer is going to be reallocated, we need that indirection. true |
| 23:05:19 | * | ekselkiu quit (Ping timeout: 260 seconds) |
| 23:06:07 | Araq | buffer growing + value semantics --> 1 indirection; buffer growing + reference semantics --> 2 indirections |
| 23:07:10 | Araq | strings are hard to design ... :-/ |
| 23:07:11 | zahary | btw the other day when we talked about case objects vs inheritance, it occurred to me that it's possible to allocate "just enough" memory for a case object in the heap if you give up the possibility for resetting the value |
| 23:07:25 | Araq | yes I know |
| 23:07:36 | Araq | case objects really want to be immutable anyway |
| 23:07:51 | Araq | and require a notion of construction |
| 23:08:24 | Araq | that's why every functional language has constructors |
| 23:08:32 | Araq | and can't do away with only functions |
| 23:12:49 | Araq | and btw 'case objects' are fine for the acyclic analysis and inhertiance is bad; every open class must be assumed to be potentially cyclic |
| 23:13:37 | zahary | statically assumed. you can still check metadata at run-time |
| 23:14:25 | Araq | good point |
| 23:14:46 | Araq | you need to register class types then but DLL support kind of requires that too |
| 23:20:07 | Araq | the compiler runs the cycle collector 7 times in total iirc |
| 23:20:52 | Araq | so it's important that most cyclic roots can really be thrown away after a cycle collection |
| 23:21:16 | Araq | what else you do in this 7 collections is mostly unimportant I think |
| 23:21:36 | Araq | so I wouldn't change to colors etc. |
| 23:21:49 | zahary | what colors do you have now? |
| 23:21:54 | Araq | I would fix the bugs and hope and pray it doesn't affect performance |
| 23:22:09 | Araq | look at line 34 |
| 23:22:12 | zahary | the actual marking algorithm needs some more colors |
| 23:22:34 | Araq | rcZct is not a color but a flag and it's used |
| 23:22:54 | Araq | the other colors are defined for the future :-) |
| 23:23:09 | Araq | but as I said the bits are already free for them |
| 23:23:12 | zahary | 2 bits unused at the moment? |
| 23:23:18 | Araq | yes |
| 23:23:21 | zahary | ok |
| 23:23:50 | zahary | well, it doesn't matter that much if we decide to increment by 16 to free another bit, does it? |
| 23:24:09 | Araq | it shouldn't |
| 23:24:31 | Araq | it would be a bit more efficient to inc/dec 1 instead of 8 though |
| 23:24:40 | Araq | as x86 has special opcodes for that |
| 23:24:53 | Araq | so the code size may shrink |
| 23:25:38 | zahary | you only have checks that refcount is effectively 0? if refcount < 8? |
| 23:25:58 | Araq | yeah in fact, I had quite some bugs with that |
| 23:26:20 | zahary | could be if (refcount << 4) == 0 (if we use the highest bits) |
| 23:26:20 | Araq | suprisingly it's harder to check against 8 then to check against 0 for me :-) |
| 23:26:42 | Araq | but that's likely to produce longer asm |
| 23:26:55 | Araq | and some cpus don't like shifts all that much |
| 23:27:03 | zahary | I have not idea, just mentioning |
| 23:28:29 | Araq | well I don't really know either, never looked at the generated assembly for all these cases |
| 23:29:12 | Araq | I only thought about I would do that in x86 |
| 23:32:42 | Araq | (btw we use the lowest bits obviously) |
| 23:41:06 | * | Vladar quit (Quit: Leaving) |
| 23:42:45 | Araq | btw instead of making cycle collection concurrent can we make it incremental instead? should be in the papers too |
| 23:43:09 | Araq | the cycle collector is the only phase of the GC that misses the 2ms deadline |
| 23:44:53 | Araq | I have to sleep now, good night |
| 23:45:01 | zahary | good night |