Filename | /home/ocbnet/domain/ocbnet.ch/vhost/webmerge/htdocs/webmerge/scripts/modules/OCBNET/Packer/2D.pm |
Statements | Executed 7129321 statements in 87.3s |
Calls | P | F | Exclusive Time |
Inclusive Time |
Subroutine |
---|---|---|---|---|---|
2372448 | 4 | 1 | 86.7s | 86.7s | findNode (recurses: max depth 63, inclusive time 2187s) | OCBNET::Packer::2D::
12 | 1 | 1 | 343ms | 87.3s | fit | OCBNET::Packer::2D::
4276 | 3 | 1 | 206ms | 206ms | splitNode | OCBNET::Packer::2D::
12 | 1 | 1 | 24.3ms | 24.3ms | CORE:sort (opcode) | OCBNET::Packer::2D::
320 | 1 | 1 | 14.0ms | 3.64s | growNode | OCBNET::Packer::2D::
164 | 1 | 1 | 12.6ms | 3.56s | growDown | OCBNET::Packer::2D::
156 | 1 | 1 | 11.9ms | 60.4ms | growRight | OCBNET::Packer::2D::
12 | 1 | 1 | 218µs | 218µs | new | OCBNET::Packer::2D::
1 | 1 | 1 | 80µs | 182µs | BEGIN@11 | OCBNET::Packer::2D::
1 | 1 | 1 | 51µs | 83µs | BEGIN@12 | OCBNET::Packer::2D::
Line | State ments |
Time on line |
Calls | Time in subs |
Code |
---|---|---|---|---|---|
1 | ################################################################################################### | ||||
2 | # Copyright 2013 by Marcel Greter | ||||
3 | # This file is part of Webmerge (GPL3) | ||||
4 | ################################################################################################### | ||||
5 | # https://github.com/jakesgordon/bin-packing/blob/master/js/packer.growing.js | ||||
6 | # Perl implementation by marcel.greter@ocbnet.ch - same license as original | ||||
7 | ################################################################################################### | ||||
8 | package OCBNET::Packer::2D; | ||||
9 | ################################################################################################### | ||||
10 | |||||
11 | 2 | 149µs | 2 | 285µs | # spent 182µs (80+103) within OCBNET::Packer::2D::BEGIN@11 which was called:
# once (80µs+103µs) by OCBNET::Spritesets::BEGIN@20 at line 11 # spent 182µs making 1 call to OCBNET::Packer::2D::BEGIN@11
# spent 103µs making 1 call to strict::import |
12 | 2 | 4.18ms | 2 | 116µs | # spent 83µs (51+33) within OCBNET::Packer::2D::BEGIN@12 which was called:
# once (51µs+33µs) by OCBNET::Spritesets::BEGIN@20 at line 12 # spent 83µs making 1 call to OCBNET::Packer::2D::BEGIN@12
# spent 33µs making 1 call to warnings::import |
13 | |||||
14 | ################################################################################################### | ||||
15 | |||||
16 | sub new | ||||
17 | # spent 218µs within OCBNET::Packer::2D::new which was called 12 times, avg 18µs/call:
# 12 times (218µs+0s) by OCBNET::Spritesets::Fit::layout at line 35 of webmerge/scripts/modules/OCBNET/Spritesets/Fit.pm, avg 18µs/call | ||||
18 | |||||
19 | 12 | 291µs | return bless {}; | ||
20 | |||||
21 | } | ||||
22 | |||||
23 | sub fit | ||||
24 | # spent 87.3s (343ms+86.9) within OCBNET::Packer::2D::fit which was called 12 times, avg 7.27s/call:
# 12 times (343ms+86.9s) by OCBNET::Spritesets::Fit::layout at line 38 of webmerge/scripts/modules/OCBNET/Spritesets/Fit.pm, avg 7.27s/call | ||||
25 | |||||
26 | 12 | 46µs | my ($self, $blocks) = @_; | ||
27 | |||||
28 | @{$blocks} = sort { | ||||
29 | ($b->{'width'} > $b->{'height'} ? $b->{'width'} : $b->{'height'}) - | ||||
30 | ($a->{'width'} > $a->{'height'} ? $a->{'width'} : $a->{'height'}) | ||||
31 | 12 | 27.7ms | 12 | 24.3ms | } @{$blocks}; # spent 24.3ms making 12 calls to OCBNET::Packer::2D::CORE:sort, avg 2.02ms/call |
32 | |||||
33 | 12 | 29µs | my ($node, $block); | ||
34 | |||||
35 | 12 | 37µs | my $len = scalar(@{$blocks}); | ||
36 | |||||
37 | 12 | 65µs | my $w = $len > 0 ? $blocks->[0]->{'width'} : 0; | ||
38 | 12 | 37µs | my $h = $len > 0 ? $blocks->[0]->{'height'} : 0; | ||
39 | |||||
40 | 12 | 187µs | $self->{'root'} = | ||
41 | { | ||||
42 | 'x' => 0, | ||||
43 | 'y' => 0, | ||||
44 | 'width' => $w, | ||||
45 | 'height' => $h | ||||
46 | }; | ||||
47 | |||||
48 | 12 | 18.7ms | for (my $n = 0; $n < $len ; $n++) | ||
49 | { | ||||
50 | |||||
51 | 4276 | 13.6ms | my $block = $blocks->[$n]; | ||
52 | |||||
53 | 4276 | 149ms | 8232 | 83.3s | if ($node = $self->findNode($self->{'root'}, $block->{'width'}, $block->{'height'})) # spent 83.1s making 4276 calls to OCBNET::Packer::2D::findNode, avg 19.4ms/call
# spent 191ms making 3956 calls to OCBNET::Packer::2D::splitNode, avg 48µs/call |
54 | { | ||||
55 | $block->{'fit'} = $self->splitNode($node, $block->{'width'}, $block->{'height'}); | ||||
56 | } | ||||
57 | else | ||||
58 | { | ||||
59 | 320 | 6.52ms | 320 | 3.64s | $block->{'fit'} = $self->growNode($block->{'width'}, $block->{'height'}); # spent 3.64s making 320 calls to OCBNET::Packer::2D::growNode, avg 11.4ms/call |
60 | } | ||||
61 | } | ||||
62 | |||||
63 | 12 | 219µs | return 1; | ||
64 | |||||
65 | }; | ||||
66 | |||||
67 | sub findNode | ||||
68 | # spent 86.7s within OCBNET::Packer::2D::findNode which was called 2372448 times, avg 37µs/call:
# 2367852 times (86.4s+-86.4s) by OCBNET::Packer::2D::findNode at line 72, avg 0s/call
# 4276 times (230ms+82.8s) by OCBNET::Packer::2D::fit at line 53, avg 19.4ms/call
# 164 times (6.08ms+3.54s) by OCBNET::Packer::2D::growDown at line 180, avg 21.6ms/call
# 156 times (39.6ms+2.08ms) by OCBNET::Packer::2D::growRight at line 152, avg 267µs/call | ||||
69 | |||||
70 | 2372448 | 5.84s | my ($self, $root, $w, $h) = @_; | ||
71 | |||||
72 | 2372448 | 50.1s | 2367852 | 0s | return $self->findNode($root->{'right'}, $w, $h) || $self->findNode($root->{'down'}, $w, $h) if $root->{'used'}; # spent 2187s making 2367852 calls to OCBNET::Packer::2D::findNode, avg 924µs/call, recursion: max depth 63, sum of overlapping time 2187s |
73 | |||||
74 | 1177324 | 2.07s | return $root if (($w <= $root->{'width'}) && ($h <= $root->{'height'})); | ||
75 | |||||
76 | 1173048 | 28.7s | return undef; | ||
77 | |||||
78 | } | ||||
79 | |||||
80 | sub splitNode | ||||
81 | # spent 206ms within OCBNET::Packer::2D::splitNode which was called 4276 times, avg 48µs/call:
# 3956 times (191ms+0s) by OCBNET::Packer::2D::fit at line 53, avg 48µs/call
# 164 times (7.76ms+0s) by OCBNET::Packer::2D::growDown at line 182, avg 47µs/call
# 156 times (6.85ms+0s) by OCBNET::Packer::2D::growRight at line 154, avg 44µs/call | ||||
82 | |||||
83 | 4276 | 13.8ms | my ($self, $node, $w, $h) = @_; | ||
84 | |||||
85 | 4276 | 17.4ms | $node->{'used'} = 1; | ||
86 | |||||
87 | 4276 | 75.7ms | $node->{'down'} = | ||
88 | { | ||||
89 | 'x' => $node->{'x'}, | ||||
90 | 'width' => $node->{'width'}, | ||||
91 | 'y' => $node->{'y'} + $h, | ||||
92 | 'height' => $node->{'height'} - $h | ||||
93 | }; | ||||
94 | |||||
95 | 4276 | 54.5ms | $node->{'right'} = { | ||
96 | 'y' => $node->{'y'}, | ||||
97 | 'height' => $node->{'height'}, | ||||
98 | 'x' => $node->{'x'} + $w, | ||||
99 | 'width' => $node->{'width'} - $w, | ||||
100 | }; | ||||
101 | |||||
102 | 4276 | 130ms | return $node; | ||
103 | |||||
104 | } | ||||
105 | |||||
106 | sub growNode | ||||
107 | # spent 3.64s (14.0ms+3.62) within OCBNET::Packer::2D::growNode which was called 320 times, avg 11.4ms/call:
# 320 times (14.0ms+3.62s) by OCBNET::Packer::2D::fit at line 59, avg 11.4ms/call | ||||
108 | |||||
109 | 320 | 1.00ms | my ($self, $w, $h) = @_; | ||
110 | |||||
111 | 320 | 1.49ms | my $canGrowDown = ($w <= $self->{'root'}->{'width'}); | ||
112 | 320 | 1.07ms | my $canGrowRight = ($h <= $self->{'root'}->{'height'}); | ||
113 | |||||
114 | # attempt to keep square-ish by growing right when height is much greater than width | ||||
115 | 320 | 1.84ms | my $shouldGrowRight = $canGrowRight && ($self->{'root'}->{'height'} >= ($self->{'root'}->{'width'} + $w)); | ||
116 | # attempt to keep square-ish by growing down when width is much greater than height | ||||
117 | 320 | 1.28ms | my $shouldGrowDown = $canGrowDown && ($self->{'root'}->{'width'} >= ($self->{'root'}->{'height'} + $h)); | ||
118 | |||||
119 | 320 | 201µs | return $self->growRight($w, $h) if ($shouldGrowRight); | ||
120 | 320 | 3.64ms | 164 | 3.56s | return $self->growDown($w, $h) if ($shouldGrowDown); # spent 3.56s making 164 calls to OCBNET::Packer::2D::growDown, avg 21.7ms/call |
121 | 156 | 3.22ms | 156 | 60.4ms | return $self->growRight($w, $h) if ($canGrowRight); # spent 60.4ms making 156 calls to OCBNET::Packer::2D::growRight, avg 387µs/call |
122 | return $self->growDown($w, $h) if ($canGrowDown); | ||||
123 | |||||
124 | # need to ensure sensible root | ||||
125 | # starting size to avoid this | ||||
126 | return undef; | ||||
127 | |||||
128 | } | ||||
129 | |||||
130 | sub growRight | ||||
131 | # spent 60.4ms (11.9+48.5) within OCBNET::Packer::2D::growRight which was called 156 times, avg 387µs/call:
# 156 times (11.9ms+48.5ms) by OCBNET::Packer::2D::growNode at line 121, avg 387µs/call | ||||
132 | |||||
133 | 156 | 515µs | my ($self, $w, $h) = @_; | ||
134 | |||||
135 | 156 | 5.10ms | $self->{'root'} = | ||
136 | { | ||||
137 | 'x' => 0, | ||||
138 | 'y' => 0, | ||||
139 | 'used' => 1, | ||||
140 | 'height' => $self->{'root'}->{'height'}, | ||||
141 | 'width' => $self->{'root'}->{'width'} + $w, | ||||
142 | 'down' => $self->{'root'}, | ||||
143 | 'right' => | ||||
144 | { | ||||
145 | 'y' => 0, | ||||
146 | 'width' => $w, | ||||
147 | 'height' => $self->{'root'}->{'height'}, | ||||
148 | 'x' => $self->{'root'}->{'width'} | ||||
149 | } | ||||
150 | }; | ||||
151 | |||||
152 | 156 | 1.73ms | 156 | 41.7ms | my $node = $self->findNode($self->{'root'}, $w, $h); # spent 41.7ms making 156 calls to OCBNET::Packer::2D::findNode, avg 267µs/call |
153 | |||||
154 | 156 | 3.48ms | 156 | 6.85ms | return $node ? $self->splitNode($node, $w, $h) : undef; # spent 6.85ms making 156 calls to OCBNET::Packer::2D::splitNode, avg 44µs/call |
155 | |||||
156 | }; | ||||
157 | |||||
158 | sub growDown | ||||
159 | # spent 3.56s (12.6ms+3.55) within OCBNET::Packer::2D::growDown which was called 164 times, avg 21.7ms/call:
# 164 times (12.6ms+3.55s) by OCBNET::Packer::2D::growNode at line 120, avg 21.7ms/call | ||||
160 | |||||
161 | 164 | 495µs | my ($self, $w, $h) = @_; | ||
162 | |||||
163 | 164 | 5.30ms | $self->{'root'} = | ||
164 | { | ||||
165 | 'x' => 0, | ||||
166 | 'y' => 0, | ||||
167 | 'used' => 1, | ||||
168 | 'width' => $self->{'root'}->{'width'}, | ||||
169 | 'height' => $self->{'root'}->{'height'} + $h, | ||||
170 | 'right' => $self->{'root'}, | ||||
171 | 'down' => | ||||
172 | { | ||||
173 | 'x' => 0, | ||||
174 | 'height' => $h, | ||||
175 | 'width' => $self->{'root'}->{'width'}, | ||||
176 | 'y' => $self->{'root'}->{'height'} | ||||
177 | } | ||||
178 | }; | ||||
179 | |||||
180 | 164 | 1.95ms | 164 | 3.54s | my $node = $self->findNode($self->{'root'}, $w, $h); # spent 3.54s making 164 calls to OCBNET::Packer::2D::findNode, avg 21.6ms/call |
181 | |||||
182 | 164 | 3.83ms | 164 | 7.76ms | return $node ? $self->splitNode($node, $w, $h) : undef; # spent 7.76ms making 164 calls to OCBNET::Packer::2D::splitNode, avg 47µs/call |
183 | |||||
184 | }; | ||||
185 | |||||
186 | 1 | 15µs | return 1; | ||
187 | |||||
188 | __DATA__ | ||||
# spent 24.3ms within OCBNET::Packer::2D::CORE:sort which was called 12 times, avg 2.02ms/call:
# 12 times (24.3ms+0s) by OCBNET::Packer::2D::fit at line 31, avg 2.02ms/call |