Meta tags:

Headings (most frequently used words):

-

Text of the page (most frequently used words):
the (76), you (25), that (24), and (22), memory (21), have (17), this (17), list (16), how (12), edge (12), function (9), malloc (8), pass (8), for (8), need (8), stb_truetype (8), all (8), but (7), performance (7), with (7), can (7), curves (7), then (7), from (7), each (7), coordinates (7), going (7), could (6), client (6), call (6), would (5), needed (5), out (5), are (5), library (5), same (5), just (5), complexity (5), without (4), makecharacterbitmapmemoryneeded (4), much (4), temp (4), than (4), build (4), active (4), programming (4), avoid (4), tesselated (4), those (4), does (4), other (4), functions (4), code (4), use (4), make (4), actually (4), time (4), allocator (4), block (4), end (4), well (3), many (3), needs (3), depends (3), number (3), edges (3), will (3), more (3), even (3), which (3), means (3), enough (3), store (3), big (3), heroic (3), get (3), first (3), instead (3), want (3), except (3), coords (3), size (3), what (3), either (3), fixed (3), internally (3), our (3), your (3), onto (3), work (3), simulation (3), point (3), newmem (3), newsize (3), truetype (2), makecharacterbitmap (2), rasterization (2), implement (2), single (2), scanline (2), see (2), maybe (2), anything (2), already (2), requires (2), significant (2), hit (2), makecharacterbitmapmemoryneededmemoryneeded (2), compute (2), above (2), way (2), shape (2), approach (2), still (2), makecharacterbitmapmemoryneededmemoryneededmemoryneeded (2), require (2), some (2), because (2), doesn (2), varying (2), parse (2), find (2), start (2), over (2), array (2), flags (2), where (2), isn (2), since (2), simply (2), requiring (2), correctly (2), sized (2), take (2), temporary (2), dynamic (2), might (2), rather (2), things (2), independently (2), little (2), don (2), determine (2), physics (2), contacts (2), determining (2), running (2), itself (2), run (2), define (2), pushing (2), every (2), suppose, trying, render, fonts, bitmaps, calling, performs, computes, latter, very, last, one, during, simultaneous, character, users, never, 100, font, specifically, won, computing, probably, unavoidably, takes, rescan, possibly, impossible, another, data, structure, computed, works, tesselate, stick, course, directly, count, building, full, lists, explicitly, not, cost, pairs, given, stores, length, visit, storing, them, fully, simultaneously, complicated, there, control, decode, huge, suck, especially, also, redo, decoding, too, writing, uglier, doing, naivest, changing, amounts, rewriting, reduce, these, mess, max, burden, set, service, pre, allocated, buffer, conceptually, portion, return, arena, suballocate, wait, freed, curve, come, minimize, usage, whether, something, equivalent, specific, case, able, allocate, beginning, growing, towards, middle, passes, figure, sizes, advance, when, reserved, say, hey, let, own, system, keeps, higher, induces, exactly, amount, fragmentation, none, fragmenting, care, about, pushes, clearer, types, libraries, example, systems, keep, between, objects, touching, variable, such, before, sort, iterative, deepening, once, per, allocation, fact, pattern, sense, standpoint, repeat, further, reuse, 1th, really, continuing, left, off, boils, down, void, null, size_t, int, apifunctionpartial, needs_more_memory, break, effect, lot, less, passing, passed, back, provide, private, mem, has, similar, behavior, person, scared, allocations, perfectly, handle, honest, name, simplifying, management, having, realloc, alt, potentially, needing, due, reallocing, tesselates, twice, final, second, fill,

Text of the page (random words):
suppose we re trying to render truetype fonts to bitmaps without calling malloc makecharacterbitmap performs rasterization makecharacterbitmapmemoryneeded computes how much temp memory to pass in how do we implement the latter function well we have many needs for memory but the very last one we ll need is for the edge list during rasterization this depends on the number of simultaneous edges on a single scanline this depends on the character 99 of users will never see more than 100 or maybe even 10 or 20 but a font could have anything in it specifically it depends on the edge list which means we ll need enough temp memory to build the edge list already we won t have memory to store the active edge list so computing how big the active edge list would be probably requires heroic programming or maybe unavoidably takes a significant performance hit as we have to rescan the edge list possibly even with heroic programming it s impossible to avoid o n 2 performance if you can t have another data structure so the client will have to pass in to makecharacterbitmapmemoryneeded enough memory to have computed the edge list so how much memory is that makecharacterbitmapmemoryneededmemoryneeded will compute the memory needed for the above function how do we implement this well we need to get the tesselated edge list how big is the tesselated edge list how do we build the tesselated edge list the way this works in stb_truetype is first we build a list of all the curves in the shape and then we tesselate it if we stick with that approach then this function still needs to build that list of curves so we need memory to store those curves so we need makecharacterbitmapmemoryneededmemoryneededmemoryneeded of course you could directly compute the count of tesselated edges from each curves without building up the full lists of curves explicitly this does not require heroic programming but it does cost you some performance that s because truetype doesn t store coordinates as x y pairs instead for a given shape it stores all of the x coordinates and then all of the y coordinates each varying length so if you want to visit all the curves without storing them you have to fully parse all the x coordinates to find the start of the y coordinates and then start over and simultaneously parse out the x coordinates and the y coordinates except it s more complicated than that first there s an array of n flags then n x coords then n y coords where the flags control how you decode the x y coords this isn t a huge performance suck especially since each of the other functions above are also going to redo this decoding too but it s still means writing the code in a much uglier way for doing this pass so for the naivest approach without changing anything in stb_truetype we d require makecharacterbitmapmemoryneededmemoryneededmemoryneeded makecharacterbitmapmemoryneededmemoryneeded makecharacterbitmapmemoryneeded makecharacterbitmap with varying amounts of rewriting of the functions we could reduce the number of these that are needed we can even avoid the active edge list mess by simply requiring the client to pass in the max of edges on a single scanline to makecharacterbitmapmemoryneeded and use that to size the memory and the burden is on the client to set that correctly but what is all that programming in service of you the client are either going to pass in some pre allocated memory buffer of fixed size or conceptually a correctly sized portion of that or you re going to call malloc and return that to us and then internally our library is going to take the temporary memory you pass in and make an arena and suballocate from it except wait our library doesn t actually need all that memory at the same time we ll have freed up the curve list by the time we have the active edge list so those can come from the same memory so if we want to minimize memory usage we actually need to use a dynamic allocator internally so whether you call malloc or use a fixed memory block we re going to internally do something equivalent to malloc actually in this specific case you might be able to just allocate from the beginning and end of the block growing towards the middle so in stb_truetype rather than have to make n passes over things to figure out those sizes in advance when you re either going to pass in an independently sized fixed size reserved block or just going to call malloc we just say hey you can either let us call malloc or you can make your own little system to malloc out of your temporary block and pass that to us that keeps our performance higher and induces exactly the same amount of fragmentation it would have i e none because it s fragmenting this temp memory that we don t care about it just pushes the complexity onto you this is clearer with other types of libraries which have to do significant work to determine things for example physics systems which need to keep list of contacts between objects touching each other those have a variable number of such contacts and determining how many are needed requires running the simulation to that point a function to determine how many are needed would itself have to run the simulation to the end and that function needs enough memory to run the simulation to just before the end i e you d end up with a sort of iterative deepening physics that you would call once per memory allocation in fact at this point and you can see this in the stb_truetype pattern as well it would make more sense from a performance standpoint to instead of running n functions that repeat all the same work and get a little further in determining how much memory is needed have each of the n functions reuse the work from the n 1th function i e each function is really continuing where it left off but what that means is that your client code boils down to void newmem null size_t newsize 0 for int code apifunctionpartial newmem newsize if code needs_more_memory break newmem malloc newsize and at this point you could get the same effect with a lot less library complexity by simply passing in an allocator function this is what stb_truetype does except the allocator function isn t passed in it s a define back to pushing the complexity onto the client stb_truetype could instead provide this private allocator from temp mem itself so you don t have to and so could every other library you call that has similar behavior but since you re the person scared of dynamic allocations i m perfectly ok with pushing that complexity onto you rather than requiring every library you might want to use to each independently handle that complexity and to be honest stb_truetype does already take a performance hit in the name of simplifying memory management to avoid you having to define a realloc alt to avoid potentially needing 2 9x the memory due to reallocing stb_truetype actually tesselates the curves twice the first time so it can find out how big the final array is and the second time to fill it out