3 ms·

Very clever use of virtual memory. Unfortunately I would expect this technique not to scale well with increasing page size, and I sure hope that we will be slo

by obl 8y ago

Very clever use of virtual memory. Unfortunately I would expect this technique not to scale well with increasing page size, and I sure hope that we will be slowly moving to >4k pages as years go by since the TLB is a very common bottleneck.

vanderZwan 8y ago
Wait, are you talking about page size, or nr of pages? Either way, that all depends on how scaling either of them up would affect the distributions of these randomized algorithms they refer to, no? > Mesh makes meshing both efficient and provably effective (with high probability) by combining it with two novel randomized algorithms. First, Mesh uses a space-efficient randomized allocation strategy that effectively scatters objects within each virtual page, making the above scenario provably exceedingly unlikely. Second, Mesh incorporates an efficient randomized algorithm that is guaranteed with high probability to quickly find candidate pages that are likely to mesh. > Meshing is only possible when no objects on the pages occupy the same offsets. A key observation is that as fragmentation increases (that is, as there are more free objects),the likelihood of successfully finding pairs of pages that mesh also increases.
grandinj 8y ago
Yeah, I agree, I wonder how the overall costs will work out, with the increased TLB pressure
nteon 8y ago
Well, there are 2 sides to increasing page sizes. If you can fit more objects on a page, there is a higher chance of collision at a given occupancy %, reducing the effectiveness of meshing. On the other hand, it means that very low occupancy pages (like single allocations) would cause an even larger amount of memory to be held onto by a process - a situation Mesh would be able to handle well. We didn't look at huge pages in the paper for the reason that today, if you care most about heap footprint you can always use 4K pages rather than 2M ones. (and lots of database-like applications, like Redis, explicitly suggest disabling huge pages)

by obl 8y ago

vanderZwan 8y ago

Wait, are you talking about page size, or nr of pages? Either way, that all depends on how scaling either of them up would affect the distributions of these randomized algorithms they refer to, no? > Mesh makes meshing both efficient and provably effective (with high probability) by combining it with two novel randomized algorithms. First, Mesh uses a space-efficient randomized allocation strategy that effectively scatters objects within each virtual page, making the above scenario provably exceedingly unlikely. Second, Mesh incorporates an efficient randomized algorithm that is guaranteed with high probability to quickly find candidate pages that are likely to mesh. > Meshing is only possible when no objects on the pages occupy the same offsets. A key observation is that as fragmentation increases (that is, as there are more free objects),the likelihood of successfully finding pairs of pages that mesh also increases.

grandinj 8y ago

Yeah, I agree, I wonder how the overall costs will work out, with the increased TLB pressure

nteon 8y ago

Well, there are 2 sides to increasing page sizes. If you can fit more objects on a page, there is a higher chance of collision at a given occupancy %, reducing the effectiveness of meshing. On the other hand, it means that very low occupancy pages (like single allocations) would cause an even larger amount of memory to be held onto by a process - a situation Mesh would be able to handle well. We didn't look at huge pages in the paper for the reason that today, if you care most about heap footprint you can always use 4K pages rather than 2M ones. (and lots of database-like applications, like Redis, explicitly suggest disabling huge pages)