Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Skyline algorithm for packing 2D rectangles

jvernay.fr

Post reply on HN
Print view View original

31–40 of 60 posts

Re: The Skyline algorithm for packing 2D rectangles

#31

Post by db48x »

joshtynjala wrote: post #30
db48x wrote: post #20

Earlier quoted context omitted.

Packing things into a GPU texture is probably the #1 most common use. If you played a game today then your computer probably spent some time packing rectangles into rectangles.

Your web browser may have also spent some time packing rectangles into rectangles. I recall reading this article a while back about how Firefox does/did it. https://mozillagfx.wordpress.com/2021/02/04/improving-textur...

That’s great; I’d forgotten about it.

Plus there are a fair few programs that render text by rendering the font into a texture atlas once and then using the GPU to copy from the atlas. Your terminal emulator may be doing this, for example.

Re: The Skyline algorithm for packing 2D rectangles

#32

Post by reader9274 »

I implemented a variation of this at Intel about 10 years ago to solve the efficient testing of microchips with different input/output pins on a limited-pin in/out tester. The goal was to efficiently load the chips in the tester to maximize utilization, with TT of each chip being the same. Fun times, heuristic-solving my way through the NP bin packing problem.

Re: The Skyline algorithm for packing 2D rectangles

#33

Post by almostgotcaught »

romesmoke wrote: post #3

An interesting variation is Dynamic Storage Allocation, in which the rectangles can slide only alongside one axis. AKA "static memory allocation", since the heights of the rectangles can be interpreted as buffer sizes, and their widths as lifetimes. Most of my PhD's effort has been devoted to beating the SOTA in this. Problem's importance nowadays is owed to deep learning's memory wall.

> Most of my PhD's effort has been devoted to beating the SOTA in this. Problem's importance nowadays is owed to deep learning's memory wall.

lol i similarly spent 1 year of my phd trying to finagle this same thing for the same exact reason. got as far as proving that when it's parameterized (like in the case of DNNs with algebraically coupled layers) it's FPT (finite parameter tractable) which is like duh but also as soon as i found that i gave up (not much more to be done ).

Re: The Skyline algorithm for packing 2D rectangles

#34

Post by guessmyname »

mikepurvis wrote: post #28
clippy99 wrote: post #8

Great writeup. Sucks when this gets asked in a coding interview to be solved in 15min :)

To be fair, in an interview context they’re probably looking for what you would implement in the mvp just to avoid getting blocked, and a brief acknowledgement that it’s an academic problem and once you have data to understand it better you’ll select and implement an appropriate algorithm after design review with colleagues.

In theory, yes, but in practice...

I’ve interviewed with several companies that asked me this specific question [1], including Facebook, ByteDance, LinkedIn, and a particular team at Apple (not my current team). The interviewers, perhaps somewhat optimistically [2], expected a fully working solution. They gave me about 40 minutes—more than the 15 minutes mentioned in the original comment—but I definitely needed the first 10-15 minutes just to get a brute-force solution running. The rest of the time was spent refining the approach and addressing 1-2 additional requirements to pass a set of visible tests.

It was challenging, but not in a traditional engineering sense. It felt more like an ACM competition [3].

Fortunately, programming skills aren’t the only thing companies assess these days. With over a decade of work experience, behavioral (experience-based) interviews now play a larger role in the final hiring decision. That said, depending on who conducts the technical portion of the interview, you could still be rejected if your code doesn’t work.

[1] https://leetcode.com/problems/the-skyline-problem/descriptio...

[2] Them, being so young ([3] https://en.wikipedia.org/wiki/Competitive_programming

Re: The Skyline algorithm for packing 2D rectangles

#35

Post by almostgotcaught »

auvi wrote: post #11
romesmoke wrote: post #3

An interesting variation is Dynamic Storage Allocation, in which the rectangles can slide only alongside one axis. AKA "static memory allocation", since the heights of the rectangles can be interpreted as buffer sizes, and their widths as lifetimes. Most of my PhD's effort has been devoted to beating the SOTA in this. Problem's importance nowadays is owed to deep learning's memory wall.

nice! you have your thesis or any related paper available online?

there are a bunch of papers on DSA from the OR people

http://adambuchsbaum.com/papers/dsa-stoc03.pdf

https://link.springer.com/chapter/10.1007/978-3-540-27798-9_...

https://users.cs.northwestern.edu/~pdinda/ics-s05/doc/dsa.pd...

there are also some from ML people trying to allocate memory optimally for DNNs:

https://arxiv.org/abs/1907.01989

https://arxiv.org/abs/1804.10001

https://arxiv.org/abs/2001.03288

they all boil down to a couple of greedy heuristics. the most recent "cool" paper was from a group at google

https://dl.acm.org/doi/10.1145/3567955.3567961

basic idea is to use both ILP and heurstics. i asked them to open source but no dice :(

Re: The Skyline algorithm for packing 2D rectangles

#36

Post by p0ckets »

almostgotcaught wrote: post #35
auvi wrote: post #11

Earlier quoted context omitted.

nice! you have your thesis or any related paper available online?

there are a bunch of papers on DSA from the OR people http://adambuchsbaum.com/papers/dsa-stoc03.pdf https://link.springer.com/chapter/10.1007/978-3-540-27798-9_... https://users.cs.northwestern.edu/~pdinda/ics-s05/doc/dsa.pd... there are also some from ML people trying to allocate memory optimally for DNNs: https://arxiv.org/abs/1907.01989 https://arxiv.org/abs/1804.10001 https://arxiv.org/abs/2001.03288 they all bo…

An even more recent one from Google: https://github.com/google/minimalloc

Re: The Skyline algorithm for packing 2D rectangles

#37

Post by almostgotcaught »

p0ckets wrote: post #36
almostgotcaught wrote: post #35

Earlier quoted context omitted.

there are a bunch of papers on DSA from the OR people http://adambuchsbaum.com/papers/dsa-stoc03.pdf https://link.springer.com/chapter/10.1007/978-3-540-27798-9_... https://users.cs.northwestern.edu/~pdinda/ics-s05/doc/dsa.pd... there are also some from ML people trying to allocate memory optimally for DNNs: https://arxiv.org/abs/1907.01989 https://arxiv.org/abs/1804.10001 https://arxiv.org/abs/2001.03288 they all bo…

An even more recent one from Google: https://github.com/google/minimalloc

i gave up on the problem about 18 months ago so i didn't keep up with the research area. is this yours? the runtimes are of course very good but i don't see a comparison on how good the approximation is vs telamalloc (or just ILP). i'll say this though: it's miraculuos that the impl is so small.

Re: The Skyline algorithm for packing 2D rectangles

#39

Post by swayvil »

I wonder how good random placement would work.

IE :

Create a number of compositions where you put everything in random locations.

Discard any compositions with overlaps.

Keep the ones with the smallest wasted space or whatever.

Also, this might be a good application for AI.

Re: The Skyline algorithm for packing 2D rectangles

#40

Post by hammock »

There is a machine in a certain wood window manufacturer's plant that I have toured, which uses lasers to measure odd pieces of wood and then table saws to cut them into necessary sized pieces, minimizing waste - even cuts for fingerjoints - it all happens on a moving belt, and it happens extremely fast and in real-time. I was impressed. Probably powered by something like this algorithm (or the MAXRECTS one)
Post reply on HN