Newest at the top
| 2026-03-10 13:50:08 +0100 | <Freakie> | I hope it doesn't sound like I'm being difficult, I'm just working with a lot of constraints (albeit intentioanlly) |
| 2026-03-10 13:49:17 +0100 | <Freakie> | at which point in-memory sharing is also problematic |
| 2026-03-10 13:48:56 +0100 | <Freakie> | the same problem can be moved to cache level |
| 2026-03-10 13:48:36 +0100 | <Freakie> | the point is more that the whole model of computation i'm working with only counts I/O operations as costful, hence *in theory* pointer sharing is problematic |
| 2026-03-10 13:47:54 +0100 | <Freakie> | it would problem be something like that if I get that far |
| 2026-03-10 13:46:55 +0100 | <comerijn> | Why not give your data a Storable instance and just allocate blocks of memory explicitly |
| 2026-03-10 13:46:39 +0100 | <Freakie> | well technically it would only matter once data needs to be pushed to the disk |
| 2026-03-10 13:46:30 +0100 | <comerijn> | *that |
| 2026-03-10 13:46:27 +0100 | <comerijn> | At the point why not take an entirely different approach |
| 2026-03-10 13:46:12 +0100 | m1dnight_ | (~m1dnight@141.134.26.23) (Ping timeout: 244 seconds) |
| 2026-03-10 13:46:05 +0100 | <Freakie> | it's nothing to do with referential transparency and everything to do with data locality |
| 2026-03-10 13:45:53 +0100 | <Freakie> | I'm trying to work with I/O efficient algorithms and sharing can imply page faults |
| 2026-03-10 13:45:48 +0100 | <comerijn> | Freakie: In an immutable setting, how do you think you could possibly observe whether something is shared? |
| 2026-03-10 13:45:16 +0100 | <comerijn> | sharing or not sharing is not obsevable |
| 2026-03-10 13:45:12 +0100 | <Freakie> | it seems counterintuitive but it's a pretty essential part (at least if the algorithms actually manage to scale to the problem sizes they want toa ddress) |
| 2026-03-10 13:44:45 +0100 | <Freakie> | yes but sharing is a problem in theory for what the algorithms need to do |
| 2026-03-10 13:44:31 +0100 | <comerijn> | A compact region is not mutable |
| 2026-03-10 13:44:13 +0100 | <comerijn> | Data is immutable |
| 2026-03-10 13:44:09 +0100 | <comerijn> | Freakie: deep copying question makes no sense |
| 2026-03-10 13:43:25 +0100 | <Freakie> | (it's desired in what I'm trying to do) |
| 2026-03-10 13:43:16 +0100 | <Freakie> | do you know if the compact regions are deep copied? |
| 2026-03-10 13:42:51 +0100 | <Freakie> | and then sorting them lazily (i.e. when you actually need to traverse said level) |
| 2026-03-10 13:42:24 +0100 | <Freakie> | otherwise I was planning on using the levelwise layout of the BDD to separate the closest data (for example what needs to be processed on the current and next level) from the priority queue itself |
| 2026-03-10 13:41:02 +0100 | <Freakie> | maybe a compact PQ could help but then I suppose the region will just keep growing till the algorithm is done? |
| 2026-03-10 13:40:33 +0100 | <Freakie> | I know, I'm just not working with many other data structures than the BDDs themselves (which are represented by lists, and only traversed during algorithms) and the priroity queue |
| 2026-03-10 13:40:31 +0100 | <comerijn> | Including (parts) of your priority queue |
| 2026-03-10 13:40:06 +0100 | <comerijn> | Freakie: I mean, you don't have to limit yourself to compact individual BDD. You can compact essentially any arbitrary tree of data |
| 2026-03-10 13:39:31 +0100 | <comerijn> | Depends how often you trigger GC ;) |
| 2026-03-10 13:39:26 +0100 | <Freakie> | I can utilize the levelwise layout of the lists though |
| 2026-03-10 13:39:12 +0100 | <Freakie> | yeah I jjust mean to say that the extra cost of traversing the input lists shouldn't be the deciding factor |
| 2026-03-10 13:38:51 +0100 | <comerijn> | Freakie: The same applies for any of the data during the algorithms :) |
| 2026-03-10 13:38:46 +0100 | <Freakie> | for n = 8 the largest BDD generated only has like 10k nodes while the number of insertions to the PQ can hit double digits |
| 2026-03-10 13:38:36 +0100 | <comerijn> | ok, so that's probably not where your cost is |
| 2026-03-10 13:38:09 +0100 | <Freakie> | the thing is just that the BDDs themselves are not that large relative to the data allocated during the algorithms |
| 2026-03-10 13:38:04 +0100 | <comerijn> | Freakie: When you create a compact region the GC copies a (transitive) data structure from the heap to a separate region, and then during GC we either free the entire region at once or only copy the pointer to the region to the new heap. Reducing GC cost from however large the data to 1 pointer |
| 2026-03-10 13:36:56 +0100 | <comerijn> | Freakie: Ok, so you have some tree data structure scattered across your heap, right? Every GC you copy that entire thing to a new heap, then wipe the old. If that tree is huge and you keep it around a long time, that's a lot of continual copying |
| 2026-03-10 13:36:52 +0100 | <Freakie> | I think it wouldn't help much though because almost all of the allocations in my program comes manipulating the priority queue (regardless of the implementation) |
| 2026-03-10 13:36:00 +0100 | <Freakie> | so basically you mean pinning the BDDs while traversing them? |
| 2026-03-10 13:35:31 +0100 | <comerijn> | Freakie: Where compact regions help is if you have a large BDD that you keep around indefinitely, by shoving it off into a compact region it basically no longer counts as live data for the GC scaling |
| 2026-03-10 13:35:31 +0100 | <Freakie> | because the children can be anywhere on a deeper level |
| 2026-03-10 13:35:17 +0100 | <Freakie> | the point of the priority queue is to extract all relevant data from a particular node before progressing past it, but there's no neat structure in terms of compactness |
| 2026-03-10 13:34:19 +0100 | <Freakie> | other times it's just traversal for e.g. satcount |
| 2026-03-10 13:34:10 +0100 | <Freakie> | a separate algorithm then builds up the BDD again |
| 2026-03-10 13:33:57 +0100 | <Freakie> | the apply algorithm takes two bdds (lists) and outputs lists of arcs that make up an unreduced bdd |
| 2026-03-10 13:33:35 +0100 | <Freakie> | yes and no? depends on the algorithm |
| 2026-03-10 13:33:16 +0100 | <comerijn> | Freakie: So you're incrementally building the representation of a BDD? |
| 2026-03-10 13:32:44 +0100 | <Freakie> | so the priority queue gives the most relevant information based on where in the list I am |
| 2026-03-10 13:32:35 +0100 | <comerijn> | Freakie: The point of regions is that you have, say 500 MB of data that is live for your entire algorithm then you reduce the GC cost of that data from "copy 500 MB" to "copy a pointer to the compact region" |
| 2026-03-10 13:32:08 +0100 | <Freakie> | yeah so I have a list representation of the BDD nodes that I need to either work on top down or bottom up; in either case I need to get as much information as possible from the input lists before proceeding to the tail |
| 2026-03-10 13:31:20 +0100 | <comerijn> | Yeah |