Thread: Container shifting methods comparison, and can I do it better?

Results 1 to 1 of 1
  1. #1 Container shifting methods comparison, and can I do it better? 
    Extreme Donator

    nbness2's Avatar
    Join Date
    Aug 2011
    Posts
    692
    Thanks given
    274
    Thanks received
    139
    Rep Power
    430
    I started this journey to find the best all-around method for shifting bank containers (when you take an item out completely and all of the items after it shift) and which one would be best for my use case, which is a low-capacity bank that you can slowly expand through in-game means. This means that I found a bunch of server sources, yoinked the code and sort of retrofitted it to work with the code I have so I can test it. I've traced a lot of these sources back to ABOUT where they were created and I've named them as such. And converted them to kotlin and optimized where I can.

    Before we go any further, I am using my own container implementations which are frankly probably not the greatest performance, but performance of those shouldn't have a significant impact on these tests (or on anything honestly). I use conventions to avoid nulls that some find odd. For example, I use InvalidItem (an impl where an item meets the conditions to be invalid, id is equal to or less than 0) in place of null. I will be using "empty" as a term for an empty slot, which in most cases is null, or in my case InvalidItem

    The Methods
    Here's a breakdown of the methods and their statistics.
    The statistics I use will be some pretty important statistics that are helpful to determine usefulness of most things in most cases, and here's the ones I'll be using. I opted out for most because median and minimum will be close enough and median is pretty much your value you can bet on having in nearly all cases.
    • minimum - The minimum time it took a call to complete. Important because this shows your best case scenario and a goal to work towards converging on
    • median - The median time it took a call to complete. Much more accurate measurement towards the majority than average.


    Here's the list of the methods used
    • nbxShift was written by me for my project NBX. Like most things I do, I don't have performance in mind initially. I am interested in writing informative code to teach people and let them explore how to do the same thing but in a different way
    • nbxPartitionShift was also written for my project. This one was more of an experiment to see how simple I could do it using the standard library. Turned out nice and cute and worked exactly how I wanted to.
    • dementhiumShift I found this in pretty much every source that used dementhium as it's base. The ones it wasn't in were the ones I rewrote. This is a really interesting one because of it's lack of interestingness.
    • codeUsaShift This almost exact code was found in a LOT of 474 to 562s. It's also relatively simple and it's beautiful.
    • rsmodShift This code works well and is written well. It looks like it actually combines some older methods, whether on purpose or purely by coincidence.


    Testing method
    Randomly generated bank container
    • All items stack
    • Only shift when a slot is empty
    • All of the slots before an empty slot are occupied

    Profiled using IntelliJ Profiler v2.8.3
    Only the shift is measured
    Each test uses a different sized container (100, 500 and 1000) but will each run 5000 times

    Method 1: NbxManual
    Spoiler for data:

    I created this while working on my current project, NBX, thinking it would be the best shift ever created and completely dependency-free. According to my findings, I didn't do too bad.
    Attached image
    The performance scales perfectly with container size which I thought was neat.
    Most of the time spent was actually getting items from the underlying array and copying an item from slot to slot.
    Item copying can be optimized by compiling exactly for 1 item class. Currently, the container can take any Item and it copies other items using a developer-provided lambda,

    Summary: Dependency free, crafted with readability in mind, scales O(size), the already-low base numbers can be optimized for specific item classes but uses generic item class

    Method 2: NbxPartitionJoin
    Spoiler for data:

    This was also used to try a much more simple to read and write shift, and it works! But the numbers are much higher. While it technically scales better, the base numbers are very large in comparison to my manual method.
    Attached image
    The performance scales pretty well relatively, but it cannot be avoided unless writing extremely specific functions because of how generic it is, using kotlin's standard library.
    Nearly all of the time was spent inside of iterators inside of Iterable<T>.partition((T) -> Boolean)

    Summary: Simple to write, scales relatively well, the high (~600% of manual) base numbers can be optimized writing specific collection functions for specific item classes

    Method 3: CodeUSA
    Spoiler for data:

    I searched a lot of older codebases and found this one throughout many of them, mostly 474-562s but there was a PI here and there that had this code as well. It's defining feature (to me) was it's lack of item class in it's containers, opting to instead use arrays of ids and arrays of amounts. I'm sure once you hit 500 million players the ram savings are nuts. But the performance savings, not so much.
    Attached image
    The base numbers were higher than expected, but it scaled not too badly.
    CodeUSA uses a simple shift where it takes a copy of the old bank, finds the empty slot and rewrites all slots past that as the items found after.
    This could probably be optimized by only rewriting the copy of all occupied slots.

    Summary: Simple once you understand, scales relatively well, the mid-range base numbers can be optimized by taking some shortcuts that weren't there in the original code

    Method 4: Dementhium
    Spoiler for data:

    This code is present in nearly all Dementhium-sourced code that I could find.
    Attached image
    Base numbers are extremely low and it actually reads a lot like CodeUSA
    It seems like the distinct feature that makes Dementhium so much faster than CodeUSA (and my code) is that it skips an iterator by emptying the entire bank container to empty and only sets slots to items that are... items.
    The vast majority of time in Dementhium is spent emptying the bank.

    Summary: Simple, quick, scales very well, seems hard to optimize in performance sense but it could be more readable (in my opinion)

    Method 5: RsMod
    Spoiler for data:

    This code is in base RsMod v1. It looks like what might be created if CodeUSA and Dementhium had a child
    Attached image
    Base numbers are startlingly high considering it looks like a mix of 2 pretty well performing algorithms.
    Most of the time is spent inside it's iterators and checking for null pointers.
    Uses an inverse method to the CodeUSA and Dementhium, starting off with an empty list, adding items that aren't empty to that list, clearing the bank and then setting from new list to bank.

    Summary: High base numbers, a seemingly bad performing combination of CodeUSA and Dementhium, can be optimized

    The second coming
    I wanted the best of all worlds and more. I took the time to understand the code and their performance and ended up creating my own monster using none of that information, really.
    Spoiler for data:

    PLEASE NOTE, the JVM could not accurately measure the 100 size shift in nanoseconds minimum so I put 25 there in lieu of the 0 it told me


    The performance scales exactly like dementhium, while readability is maintained.
    While analyzing the code, I realized most of the time spent inside of it was simply finding the index of the first empty. I took it a step further and modified my container to keep track of the first empty slot using it's remove function and if it removes an item that empties the slot then it sets the firstEmptySlot variable to the slot it just emptied.
    I also realized that same thing with finding the second empty slot, and started keeping track of that.
    The performance gains were really really nice and the readability didn't suffer while also reducing LOC.
    Attached image
    I've conquered dementhium

    These gains were powered by keeping track of the empty slots and will never be more useful than most others in a real scenario but

    Here's the code gist

    summary: i optimized dementhium away

    Not done making container, but it will come with something even better
    KT/JAVA - NBX 637 - HERE!
    KT - Drop table 4: Flexible, Powerful - HERE!
    KT - Command: Simplify writing commands - HERE
    KT - NbUtil: Make your kotlin easier - HERE
    KT - Hopping Islands: From Java to Kotlin - P1 - P2 - P3 - P4 - P5
    Reply With Quote  
     

  2. Thankful user:



Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. Replies: 1
    Last Post: 02-03-2016, 12:20 AM
  2. Very quick fix just can't do it -_-
    By .java in forum Help
    Replies: 5
    Last Post: 01-03-2012, 12:44 AM
  3. Can I do it?
    By Inclement in forum Help
    Replies: 2
    Last Post: 11-07-2011, 10:33 AM
  4. Can I do it?
    By Inclement in forum Help
    Replies: 1
    Last Post: 11-07-2011, 10:32 AM
  5. it is possible.. if yes how can i do it?
    By foxxypopo in forum Help
    Replies: 4
    Last Post: 11-04-2009, 01:27 AM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •