It took me three weeks of design, redesign, more redesign, lots of implementing scattered within, and three intense days of debugging a giant mass of previously untested code, but I finally have a basic modular system in place for running all procedural generation from Lua. This will enable me (and eventually anyone else) to quickly experiment with various algorithms for every stage of planet creation and presentation.
Unfortunately, I have a lot of optimizing investigations to do, because it seems to be running about 100 times slower than the prior C++ code. But at least it generates the exact same planet (give or take a few subtle discrepancies due to slightly different math here and there). Based on some of my earlier experiments at the beginning of the month, I’m pretty sure I can bring that up to within at least 10% of the speed of my C++ implementation, and quite possibly within 50% of its speed. Just need to profile and figure out the bottlenecks. (Edit: A day’s worth of investigation has gotten me up to around 13%, or 7.5 times slower than the C++ implementation. That should be acceptable for the moment.)
A cool thing about the architecture I ended up with is that not only will it naturally support a rich modularity of hooking up algorithms at different stages to each other, but that the way this modularity is exposed will also automatically enable a significant degree of concurrent execution on multiple cores with little to no effort on the part of the script writer. Right now I have only implemented a single threaded execution model, but I should be able to change these details under the hood when I get to that stage in the project, and the Lua scripts won’t know the difference. If you’re curious, allow me to provide an overview of how I’ve designed this modularity and concurrency.
At the heart of this design is what I am boringly calling a module. Each module describes the type of resources that it works with, and the nature of how it works with them. On a basic level, these are a module’s inputs and outputs. But to give the execution engine more details to work with, I offer more granular usages. So far I have read, create, write (to an existing resource), and modify (read & write). Additionally, each of can be specified with per-element usage, indicating that the resource is a collection, and each element in the collection is needed independently of the rest.
The type of each resource is given by a combination of its storage type and semantics that describe what the resource’s data represents. So far the semantics are just a string, though I’m aware of some important features that will probably require some greater sophistication.
Here’s an example of a module definition that computes the centroid of each triangle in a mesh:
1 2 3 4 5 |
Module("CalculateMeshFaceCentroids") :ReadElements(Array[FixedArray[UInt32][3]], "mesh/face/vertexIndices") :Read(Array[Vector3[Q1616]], "mesh/vertex/position") :CreateElements(Array[Vector3[Q1616]], "mesh/face/centroid") :Do(CalculateMeshFaceCentroids) |
The faces are each just a three-element array of indices referencing into the vertex position array. (The number type I’m using here, Q1616
, is a fixed point type with 16 bits for the integral portion and 16 bits for the fractional portion.) This module states that it only needs to read one face at a time and creates one centroid at a time, though it needs the entire vertex position array available and unmodified throughout the entire operation, since each face could refer to potentially any vertex in the array. The actual execution of the operation is implemented elsewhere, in the function CalculateMeshFaceCentroids()
. When executed, instances of the three resources described will be acquired from earlier modules or created, and will be passed to the function in the order in which they were defined above. The code ends up looking something like this:
1 2 3 4 5 6 7 8 9 10 |
local function CalculateMeshFaceCentroids(faceVertexIndices, vertexPositions, faceCentroids) faceCentroids:Reserve(faceVertexIndices.size) for i = 0, faceVertexIndices.size - 1 do local vertexIndices = faceVertexIndices[i] faceCentroids:PushBack(( vertexPositions[vertexIndices[0]] + vertexPositions[vertexIndices[1]] + vertexPositions[vertexIndices[2]]) / 3) end end |
This isn’t so awful, but it’s leaving a lot of parallelism unutilized. This is essentially just a map operation, mapping each input element to exactly one output element, and is disgustingly parallelizable. So I’ve provided an object that can wrap the details of a particular map operation and return it to the execution engine to execute as it sees fit. As I stated earlier, I’m not taking advantage of it yet, but the script can already be written such that it will take advantage of it when it’s available. The centroid function could be rewritten as follows:
1 2 3 4 5 6 7 8 9 |
local function CalculateMeshFaceCentroids(faceVertexIndices, vertexPositions, faceCentroids) return Map() :From(faceVertexIndices) :To(faceCentroids) :Do(function(vertexIndices) return ( vertexPositions[vertexIndices[0]] + vertexPositions[vertexIndices[1]] + vertexPositions[vertexIndices[2]]) / 3 end) end |
The map operation is told what its per-element inputs and outputs are, and what action to take with each input to generate each output. The inner action only needs to receive one input, a single face, since the closure captures the vertex position array as an upvalue. The return value of this inner action is then automatically inserted into the face centroids array behind the scenes by the execution engine that is executing the map operation.
You’ll note that this design also works incredibly well with the data-oriented design paradigm that I’m trying to utilize more and more in my software architecture. In particular, as above, I plan on using the struct-of-arrays pattern more often than the common array-of-structs that is prevalent in a lot of object-oriented design. This makes it easier for each module to access precisely and only the data that it needs, increasing opportunities for executing different modules concurrently. It will also improve utilization of the cache since loops won’t be iterating over large arrays that contain a lot of cold data, but will only be iterating over tight arrays of hot data.
We’ll see how it pans out over the coming months, but I’m feeling pretty pleased so far with the overall design.
I’m also very pleased with how my data type utilities turned out, with the aid of syntactic sugar from using Lua’s metatable system. I want to go into some detail about I implemented these types, but I should save that for another post. Especially since some of the details are likely to change over the next week as I poke aggressively at the performance issues. I know LuaJIT is capable of some incredible efficiency for a dynamic language, but I’m probably abusing it in a variety of ways that will hopefully make themselves known and be resolvable without ruining my design which is currently relatively clean.
80 Comments
Are you doing a lot of calls into C code? LuaJIT is generally really good with pure Lua, but it can’t do much with foreign function calls. Of course, LuaJIT may have other weakness I’m unaware of, but 10x slower is pretty far outside the norm.
@Nasarius, Thanks for the tip! For the most part I’m successfully remaining fully within the Lua environment, avoiding calling out to C. What I saw a lot yesterday were a wide variety of odds and ends that were causing trace aborts, and the interpreted code was running drastically slower than when it could be successfully compiled. If I were just using doubles, I suspect I would have avoided many of the problems. But since I’m using a fixed point representation, I have to be a bit more careful.
At the beginning of the day, each iteration of building a planet with my current settings took around 5 seconds. Each optimization step I took focused on one or two stages of generation at a time, and often shaved off as much as half a second from the run time. I’m now down to around 0.3 seconds per iteration, and I wouldn’t be surprised if I can find one or two remaining culprits that are ruining a small portion of the logic, causing it to irresponsibly take a proportionally large chunk of time to execute. If I can take out another 0.2 to 0.25 seconds, that’ll get me to the 50% speed of compiled code that I’m aiming for.
A prime suspect at this point is my temporary use of math functions like sqrt() and sin(). For these I’m currently converting my fixed point numbers to double, calling the math function, and then converting back to fixed point. I suspect I’ll see some notable improvements once I provide native fixed point implementations, but that’ll take more time than the optimizations I’ve already done.
In the end I’ll probably need to start looking at the generated bytecode. It’s not entirely clear to me at the moment when LuaJIT is willing to use integers and when it is using doubles, so I don’t know if my usage patterns with array indexes are causing a lot of conversions between the two. That could introduce a fair bit of useless overhead. There might be other surprises that I’m not even thinking of either, but are possibly obvious and easy to fix once realized.
Trackback by writeaessay — 2018/05/27 @ 11:56
write an essay for me http://gsgfsdgfdhjhjhj.com/
Kudos, Plenty of information!
Trackback by URL — 2019/03/25 @ 10:57
… [Trackback]
[…] There you will find 8253 more Infos: experilous.com/1/blog/post/modular-procedural-generation-with-lua/trackback […]
Trackback by Homepage — 2019/10/13 @ 08:13
… [Trackback]
[…] Read More Infos here: experilous.com/1/blog/post/modular-procedural-generation-with-lua […]
Trackback by a fantastic read — 2020/01/19 @ 17:50
a fantastic read
Experilous: Modular Procedural Generation with Lua
Trackback by deltasone generic — 2020/03/09 @ 23:37
deltasone generic
Experilous: Modular Procedural Generation with Lua
Trackback by inhalers online — 2020/03/19 @ 14:39
inhalers online
Experilous: Modular Procedural Generation with Lua
Trackback by ciprofloxacin order — 2020/04/23 @ 06:56
ciprofloxacin order
Experilous: Modular Procedural Generation with Lua
Trackback by low dose naltrexone prescription — 2020/04/27 @ 21:52
low dose naltrexone prescription
Experilous: Modular Procedural Generation with Lua
Trackback by buy careprost online — 2020/05/05 @ 03:07
buy careprost online
Experilous: Modular Procedural Generation with Lua
Trackback by tylenol anti inflammatory medication — 2020/05/06 @ 04:03
tylenol anti inflammatory medication
Experilous: Modular Procedural Generation with Lua
Trackback by chloroquine malaria prophylaxis — 2020/05/07 @ 03:37
chloroquine malaria prophylaxis
Experilous: Modular Procedural Generation with Lua
Trackback by can you buy hydroxychloroquine over the counter — 2020/05/29 @ 23:25
can you buy hydroxychloroquine over the counter
Experilous: Modular Procedural Generation with Lua
Trackback by careprost 3ml eye drops — 2020/07/12 @ 00:53
careprost 3ml eye drops
Experilous: Modular Procedural Generation with Lua
Trackback by buy hydroxychloroquine online — 2020/08/09 @ 18:22
buy hydroxychloroquine online
Experilous: Modular Procedural Generation with Lua
https://www.ekffo150.com 우리카지노사이트
https://www.skfl4949.com/firstcasino 퍼스트카지노
https://www.skfl4949.com/meritcasino 메리트카지노
https://www.skfl4949.com/sandscasino 샌즈카지노
https://www.skfl4949.com/thekingcasino 더킹카지노
https://www.skfl4949.com/yescasino 예스카지노
https://www.skfl4949.com/ 우리카지노사이트
Trackback by 토토사이트 — 2021/09/21 @ 09:08
토토사이트
Experilous: Modular Procedural Generation with Lua
It is difficult to find a piece of office furniture that you like. We are a professional Modern employee desk factory. Our office furniture is not only comfortable, but also of high quality and good value.
Trackback by sex games .gif — 2021/12/07 @ 08:06
sex toy party games https://cybersexgames.net/
Trackback by wild casino online — 2021/12/12 @ 14:40
sugarhouse casino online sportsbook https://casinogamesmachines.com/
Trackback by keto — 2021/12/14 @ 09:14
shark tank keto https://ketogenicdiets.net/
Trackback by keto creme brulee — 2021/12/14 @ 11:43
what is keto flu https://ketogendiet.net/
Trackback by keto app — 2021/12/15 @ 07:10
keto diet snacks https://ketogenicdietinfo.com/
Trackback by is squash keto — 2021/12/15 @ 10:35
keto meal https://ketogendiets.com/
Trackback by writing an argument essay — 2021/12/15 @ 14:59
essays on writing https://anenglishessay.com/
Trackback by writing essay help — 2021/12/15 @ 22:46
persuasive writing essays https://topessayswriter.com/
Trackback by writing an autobiography essay — 2021/12/17 @ 03:21
writing narrative essay https://howtowriteessaytips.com/
Trackback by what to write my college essay about — 2021/12/17 @ 06:47
what to write college essay about https://checkyouressay.com/
Trackback by gay dating websites usa — 2021/12/17 @ 09:15
gay dating in qatar https://gayprideusa.com/
Trackback by best gay dating site for asia — 2021/12/17 @ 11:54
dating orlando gay https://gayfade.com/
Trackback by books gay dating — 2021/12/17 @ 13:24
gay sugar daddies dating https://gaysugardaddydatingsites.com/
Trackback by critical thinking vs analytical thinking — 2021/12/19 @ 11:46
critical thinking com https://criticalthinkinginstitute.com/
Trackback by critical thinking foundation — 2021/12/19 @ 13:10
critical thinking essay https://criticalthinking2020.net/
Trackback by define: critical thinking — 2021/12/19 @ 14:22
critical thinking film https://uncriticalthinking.com/
Trackback by reflective essay — 2021/12/19 @ 16:44
how long is a essay https://choosevpn.net/
Trackback by thesis in an essay — 2021/12/19 @ 18:37
essay title examples https://topvpndeals.net/
Trackback by covid 19 essay — 2021/12/19 @ 21:25
structure of an essay https://tjvpn.net/
Trackback by another word for however in an essay — 2021/12/19 @ 23:37
essay conclusion https://thebestvpnpro.com/
Trackback by how to write a hook in an essay — 2021/12/20 @ 01:57
5 paragraph essay example https://vpn4home.com/
Trackback by dbq essay example — 2021/12/20 @ 02:16
correct essay https://vpnshroud.com/
Trackback by what is a collage essay — 2021/12/20 @ 04:20
rhetorical analysis essay example (pdf) https://vpnsrank.com/
Trackback by persuasive essay format — 2021/12/20 @ 06:34
400 word essay https://vpn4torrents.com/
Trackback by common application essay — 2021/12/20 @ 08:42
research essay examples https://windowsvpns.com/
เว็บสล็อต
Apply for online gambling websites, casinos, online slots, the best websites in the world of gambling. No minimum deposit, real money, real rich.
Trackback by 1december — 2021/12/31 @ 04:59
1mushroom
Trackback by gay dating hookup — 2022/01/02 @ 06:56
gay bear dating https://gaypridee.com
Trackback by gay dating charlotte nc — 2022/01/02 @ 07:54
gay interracial dating sarasota https://gay-buddies.com
Trackback by gay dating charlotte nc — 2022/01/02 @ 09:56
dating for older gay men https://speedgaydate.com
Trackback by gay dating official site — 2022/01/02 @ 10:46
indy gay dating free https://gayfade.com
Trackback by gay massachusetts chat no sign up — 2022/01/14 @ 06:43
snap chat gay boy dick https://bjsgaychatroom.info/
Trackback by white gay liberal dating interracial to avoid being seen as racist — 2022/01/14 @ 07:17
gay macho dating https://gaypridee.com/
Trackback by gay rulette chat — 2022/01/14 @ 12:27
gay cruising chat https://gaytgpost.com/
Trackback by chat de gay usa — 2022/01/14 @ 15:52
gay video cam chat https://gay-buddies.com/
Trackback by dating gay costa rican — 2022/01/15 @ 05:58
gay dating army scam https://speedgaydate.com/
Trackback by kitty glitter slots — 2022/01/28 @ 10:40
casino slots https://2-free-slots.com/
Trackback by slots of montana — 2022/01/28 @ 15:19
gsn casino slots free https://freeonlneslotmachine.com/
Trackback by gsn casino free slots — 2022/01/28 @ 19:30
8pm news slots https://candylandslotmachine.com/
Trackback by brian christopher slots — 2022/01/28 @ 22:55
bier haus slots https://pennyslotmachines.org/
Trackback by my konami slots — 2022/01/29 @ 02:45
free no downloads slots https://slotmachinesworld.com/
Trackback by free slots machines — 2022/02/03 @ 12:23
double down slots https://slotmachinesforum.net/
Trackback by san manuel online slots — 2022/02/03 @ 15:39
d
Trackback by las vegas slots for free — 2022/02/03 @ 18:44
ruby slots casino login https://beat-slot-machines.com/
Trackback by mirror ball slots — 2022/02/03 @ 21:06
wow equipment slots https://download-slot-machines.com/
Trackback by 459 free casino slots — 2022/02/04 @ 00:08
hollywood slots in bangor https://411slotmachine.com/
Trackback by king kong slots — 2022/02/04 @ 08:03
inferno slots https://slotmachinegameinfo.com/
Trackback by spss dissertation help — 2022/02/10 @ 13:09
writing methodology for dissertation https://buydissertationhelp.com/
Trackback by help with my dissertation proposal — 2022/02/11 @ 10:33
dissertation methodology design help https://dissertationwriting-service.com/
Trackback by help with dissertation research — 2022/02/11 @ 14:35
dissertation examples https://help-with-dissertations.com/
Trackback by dissertation help in houston — 2022/02/11 @ 15:50
online law dissertation help https://mydissertationwritinghelp.com/
Trackback by cheap dissertation help in chicago — 2022/02/11 @ 20:35
writing chapter 4 of dissertation https://dissertations-writing.org/
Trackback by cultural studies dissertation help — 2022/02/11 @ 22:59
site:tickettailor.com dissertation help https://helpon-doctoral-dissertations.net/
Some really great blog posts on this site, thanks for your contribution. Best Tesla Accessories
Trackback by 사다리게임 — 2022/04/17 @ 18:40
사다리게임
Experilous: Modular Procedural Generation with Lua
Leave a comment