| sadmac2 | Keybuk: for the lists, what if we swapped the prev and next pointers for cursors? | 15:27 |
|---|---|---|
| sadmac2 | if list->next->prev != self (list->next is a cursor) | 15:28 |
| Keybuk | huh? | 15:30 |
| sadmac2 | Keybuk: for cursors, cursor->next points to the previous element, and cursor->prev points to the next. We can detect this condition easily. if list->next->prev != list then list->next is a cursor | 15:31 |
| Keybuk | there's lots of ways like that | 15:32 |
| Keybuk | but they all invalidate the list in such a way that you can't just iterate on list->next | 15:32 |
| sadmac2 | Keybuk: well, in the list head right now, the ordering is the only bit of information that isn't used | 15:35 |
| sadmac2 | well, it is used, but that can be parted with | 15:35 |
| Keybuk | ? | 15:36 |
| sadmac2 | Keybuk: if you're serious about making this multithreaded one day, I suggest you just add the flag variable, because you're going to have to put a semaphore in the list head later anyway, so the space is going to get used. | 15:37 |
| Keybuk | the flag still means you have to know about cursors | 15:38 |
| Keybuk | which means an nih_list_next () and nih_list_prev () function | 15:38 |
| Keybuk | (that know how to skip over them) | 15:38 |
| sadmac2 | macros more like | 15:38 |
| sadmac2 | and that's the nature of the problem | 15:38 |
| sadmac2 | the stock linked list just doesn't display reentrant behavior | 15:38 |
| Keybuk | they have to be while loops | 15:38 |
| Keybuk | with a temporary variable at least | 15:39 |
| Keybuk | for (NihList *ptr = iter; ptr != iter && nih_list_is_cursor (ptr); ptr = ptr->next) | 15:40 |
| Keybuk | ; | 15:40 |
| sadmac2 | Keybuk: you're next solution, from what I can gather, is to drop linked lists altogether. I can solve these sorts of issues slightly better with an auto-array | 15:41 |
| Keybuk | how does that help? | 15:50 |
| Keybuk | at the point you're not using a linked list, you're in strange territory that's rarely worth bothering with | 15:53 |
| sadmac2 | what?? | 17:07 |
| sadmac2 | an auto array helps because next and prev can be calculated for items that have gone out of existence | 17:08 |
| sadmac2 | prev for foo[i] is foo[i-1] | 17:08 |
| sadmac2 | and I really don't think linked list are that special | 17:09 |
| ion_ | #define NIH_LIST_FOREACH_SAFE(list, i) \ | 17:32 |
| ion_ | for (NihList *_copy_##i = nih_list_dup (list), *_##i = 0; \ | 17:32 |
| ion_ | *(int *)&_##i < 2; ++ *(int *)&_##i) \ | 17:32 |
| ion_ | if (*(int *)&_##i == 1) nih_free (_copy_##i); \ | 17:32 |
| ion_ | else NIH_LIST_FOREACH (_copy_##i, i) | 17:32 |
| ion_ | Wait. No, it wouldn’t work. | 17:34 |
| ion_ | I didn’t think far enough. :-) | 17:40 |
| Keybuk | heh, copy the list? | 17:55 |
| Keybuk | has the same basic problem, you can't free the current or next pointer | 17:55 |
| sadmac2 | I don't think linked lists are right here | 17:56 |
| Keybuk | sadmac2: any option has the same fundamental problem | 17:56 |
| sadmac2 | Keybuk: Ordered vector + iterators listed in head structure fixes it | 17:57 |
| Keybuk | ?! | 17:58 |
| sadmac2 | remove(list, x) { list.values[x] = list.values[--list.size]; for( k in list.iters) { if k >= x; k-- } } | 17:58 |
| sadmac2 | being able to iterate by an index number rather than a pointer has its advantages | 17:59 |
| Keybuk | which means you can't reference from anywhere else | 17:59 |
| Keybuk | because the pointer to the object changes | 17:59 |
| Keybuk | so you have to refer by index *everywhere* | 17:59 |
| Keybuk | Job * becomes guint32 job_idx | 17:59 |
| sadmac2 | not quite everywhere | 18:00 |
| sadmac2 | only where list location is relevant | 18:00 |
| Keybuk | no, everywhere | 18:00 |
| Keybuk | because the pointer will change if you move it in the array | 18:00 |
| sadmac2 | Keybuk: ah, but you can still have a list head in the objects | 18:00 |
| Keybuk | if you have a list head, then it's a linked list | 18:00 |
| Keybuk | not a vector | 18:00 |
| sadmac2 | foojob->list_idx | 18:00 |
| sadmac2 | the head contains a pointer to a parent list and its index number therein | 18:01 |
| Keybuk | vectors are also insanely expensive to do inserts on | 18:01 |
| sadmac2 | Keybuk: I just did it in O(1) | 18:01 |
| Keybuk | it's O(len list) | 18:01 |
| sadmac2 | Keybuk: its only expensive if you preserve order | 18:01 |
| Keybuk | your above was not O(1) | 18:02 |
| sadmac2 | it was O(1 + num iters) | 18:02 |
| Keybuk | which leaves holes in the list | 18:02 |
| sadmac2 | no | 18:03 |
| sadmac2 | to remove 1) remove last element 2) put it back on top of the element you want gone 3) count-- | 18:03 |
| Keybuk | that doesn't preserve order | 18:03 |
| sadmac2 | nope | 18:03 |
| * Keybuk is writing an init daemon, not a STL | 18:04 | |
| sadmac2 | well you've seen all the defects of all the possible solutions | 18:04 |
| sadmac2 | which one do you want to live with? | 18:04 |
| Keybuk | honestly, I don't have a problem with the solution we had before | 18:05 |
| sadmac2 | which is? | 18:05 |
| Keybuk | I still can't see why you're affected by it | 18:05 |
| Keybuk | cache the next pointer | 18:05 |
| sadmac2 | fix my segfaults plz | 18:06 |
| Keybuk | you haven't filed any bugs | 18:06 |
| Keybuk | nor have you attached any core files | 18:06 |
| Keybuk | or stack traces | 18:06 |
| Keybuk | etc. | 18:06 |
| sadmac2 | notting: can you help here^^ | 18:07 |
| notting | oof. basically, when exiting single user mode, we would get random crashes and segfaults | 18:08 |
| notting | but i don't have a trace with current code at the moment | 18:08 |
| sadmac2 | notting: I don't think we've pushed anything new since 0.5.0 that would change this, and since it seems to be race-related, probably best to reproduce it on the code that failed | 18:09 |
| * sadmac2 goes to class | 18:11 | |
| Keybuk | this is much easier in a reference/gc language :) | 18:21 |
| notting | init.js | 18:26 |
| Keybuk | init.cs | 18:27 |
| Keybuk | the real problem is just that the nih main loop code sucks | 18:30 |
| Keybuk | if I fix that, then the "best way to line up a series of data structures" debate goes away :p | 18:30 |
| ion_ | Switch to... glib! | 18:31 |
| * ion_ ducks | 18:31 | |
| Keybuk | tempting | 18:34 |
| sadmac2 | Keybuk: I'm pretty sure we fixed the main looop | 19:41 |
| sadmac2 | we were getting an analogous issue elsewhere | 19:41 |
| sadmac2 | the fix wasn't great I grant you, but I think that instance of the bug went away | 19:42 |
| Keybuk | given the main loop is the only place this pattern is used, it might simply be not in the loop functions | 19:42 |
| Keybuk | ie in the timer or child or signal code | 19:42 |
| Keybuk | by "fix the main loop" I include those | 19:42 |
| sadmac2 | Keybuk: the other option is to do your multiparent allocator and fix it that way | 19:42 |
| Keybuk | I believe by doing both, I can eliminate all uses of _SAFE in the first place | 19:43 |
| sadmac2 | Keybuk: i.e. instead of caching the next pointer, the loop simply becomes a parent as it iterates | 19:43 |
| sadmac2 | yes | 19:43 |
| === Keybuk_ is now known as Keybuk | ||
Generated by irclog2html.py 2.7 by Marius Gedminas - find it at mg.pov.lt!