The main purpose of this class is to optimize the use of contiguous
space in GPU memory. Each contiguous memory block can be drawn in a
single call. The starts index of each block is kept by starts,
and the end + 1 by
ends`.
The data can be compressed by a call to defragment
.
intrude import gamnit::flat
var array = new GroupedArray[String]
assert array.to_s == ""
array.add "a"
array.add "b"
array.add "c"
array.add "d"
array.add "e"
array.add "f"
assert array.to_s == "[a,b,c,d,e,f]"
assert array.capacity == 6
array.remove "a"
assert array.to_s == "[b,c,d,e,f]"
array.remove "b"
assert array.to_s == "[c,d,e,f]"
array.remove "f"
assert array.to_s == "[c,d,e]"
array.remove "d"
assert array.to_s == "[c][e]"
array.add "A"
assert array.to_s == "[A][c][e]"
array.add "B"
assert array.to_s == "[A,B,c][e]"
array.remove "e"
assert array.to_s == "[A,B,c]"
array.add "D"
assert array.to_s == "[A,B,c,D]"
array.add "E"
assert array.to_s == "[A,B,c,D,E]"
assert array.capacity == 6
assert array.length == 5
array.remove "A"
array.remove "B"
array.remove "c"
array.remove "D"
array.remove "E"
assert array.to_s == ""
array.add "a"
assert array.to_s == "[a]"
gamnit :: GroupedArray :: available=
List of available slotsgamnit :: GroupedArray :: defaultinit
gamnit :: GroupedArray :: defragment
Defragment and compress everything into a single chunks beginning at 0gamnit $ GroupedArray :: SELF
Type of this instance, automatically specialized in every classgamnit :: GroupedArray :: available=
List of available slotscore :: Object :: class_factory
Implementation used byget_class
to create the specific class.
gamnit :: GroupedArray :: defaultinit
core :: Object :: defaultinit
gamnit :: GroupedArray :: defragment
Defragment and compress everything into a single chunks beginning at 0core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
core :: Object :: native_class_name
The class name of the object in CString format.core :: Object :: output_class_name
Display class name on stdout (debug only).GroupedArray
to use Sprite::context_index
and avoid using index_of
# Representation of sprite data on the GPU
#
# The main purpose of this class is to optimize the use of contiguous
# space in GPU memory. Each contiguous memory block can be drawn in a
# single call. The starts index of each block is kept by `starts,
# and the end + 1 by `ends`.
#
# The data can be compressed by a call to `defragment`.
#
# ~~~
# intrude import gamnit::flat
#
# var array = new GroupedArray[String]
# assert array.to_s == ""
#
# array.add "a"
# array.add "b"
# array.add "c"
# array.add "d"
# array.add "e"
# array.add "f"
# assert array.to_s == "[a,b,c,d,e,f]"
# assert array.capacity == 6
#
# array.remove "a"
# assert array.to_s == "[b,c,d,e,f]"
#
# array.remove "b"
# assert array.to_s == "[c,d,e,f]"
#
# array.remove "f"
# assert array.to_s == "[c,d,e]"
#
# array.remove "d"
# assert array.to_s == "[c][e]"
#
# array.add "A"
# assert array.to_s == "[A][c][e]"
#
# array.add "B"
# assert array.to_s == "[A,B,c][e]"
#
# array.remove "e"
# assert array.to_s == "[A,B,c]"
#
# array.add "D"
# assert array.to_s == "[A,B,c,D]"
#
# array.add "E"
# assert array.to_s == "[A,B,c,D,E]"
# assert array.capacity == 6
# assert array.length == 5
#
# array.remove "A"
# array.remove "B"
# array.remove "c"
# array.remove "D"
# array.remove "E"
# assert array.to_s == ""
#
# array.add "a"
# assert array.to_s == "[a]"
# ~~~
private class GroupedArray[E]
# Memory with actual objects, and null in empty slots
var items = new Array[nullable E]
# Number of items in the array
var length = 0
# Number of item slots in the array
fun capacity: Int do return items.length
# List of available slots
var available = new MinHeap[Int].default
# Start index of filled chunks
var starts = new List[Int]
# Index of the spots after filled chunks
var ends = new List[Int]
# Add `item` to the first available slot and return its index
fun add(item: E): Int
do
length += 1
if available.not_empty then
# starts & ends can't be empty
var i = available.take
items[i] = item
if i == starts.first - 1 then
# slot 0 free, 1 taken
starts.first -= 1
else if i == 0 then
# slot 0 and more free
starts.unshift 0
ends.unshift 1
else if starts.length >= 2 and ends.first + 1 == starts[1] then
# merge 2 chunks
ends.remove_at 0
starts.remove_at 1
else
# at end of first chunk
ends.first += 1
end
return i
end
items.add item
if ends.is_empty then
starts.add 0
ends.add 1
else ends.last += 1
return ends.last - 1
end
# Remove the first instance of `item`
fun remove(item: E)
do
var index = items.index_of(item)
remove_at(item, index)
end
# Remove `item` at `index`
fun remove_at(item: E, index: Int)
do
var i = index
length -= 1
items[i] = null
var ii = 0
for s in starts, e in ends do
if s <= i and i < e then
if s == e-1 then
# single item chunk
starts.remove_at ii
ends.remove_at ii
if starts.is_empty then
items.clear
available.clear
return
end
else if e-1 == i then
# last item of chunk
ends[ii] -= 1
else if s == i then
# first item of chunk
starts[ii] += 1
else
# break up chunk
ends.insert(ends[ii], ii+1)
ends[ii] = i
starts.insert(i+1, ii+1)
end
available.add i
return
end
ii += 1
end
abort
end
# Defragment and compress everything into a single chunks beginning at 0
#
# Returns the elements that moved as a list.
#
# ~~~
# intrude import gamnit::flat
#
# var array = new GroupedArray[String]
# array.add "a"
# array.add "b"
# array.add "c"
# array.add "d"
# array.remove "c"
# array.remove "a"
# assert array.to_s == "[b][d]"
#
# var moved = array.defragment
# assert moved.to_s == "[d]"
# assert array.to_s == "[d,b]"
# assert array.length == 2
# assert array.capacity == 2
#
# array.add "e"
# array.add "f"
# assert array.to_s == "[d,b,e,f]"
# ~~~
fun defragment(max: nullable Int): Array[E]
do
app.perf_clock_sprites.lapse
max = max or else length
var moved = new Array[E]
while max > 0 and (starts.length > 1 or starts.first != 0) do
var i = ends.last - 1
var e = items[i]
assert e != null
remove e
add e
moved.add e
max -= 1
end
if starts.length == 1 and starts.first == 0 then
for i in [length..capacity[ do items.pop
available.clear
end
sys.perfs["gamnit flat gpu defrag"].add app.perf_clock_sprites.lapse
return moved
end
redef fun to_s
do
var ss = new Array[String]
for s in starts, e in ends do
ss.add "["
for i in [s..e[ do
var item: nullable Object = items[i]
if item == null then item = "null"
ss.add item.to_s
if i != e-1 then ss.add ","
end
ss.add "]"
end
return ss.join
end
end
lib/gamnit/flat/flat_core.nit:1480,1--1716,3