• Advertisement
Sign in to follow this  

Unity Implementing a C# Sorting Network Library

This topic is 413 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,
 
As a game programmer who often prototypes and designs in Unity, I've delved into general C# optimizations for the sake of good practice over the last while. Recently I've been using sorting networks instead of common algorithms for small arrays, and since I coulnd't locate a simple C# library with Bose-Nelson sorts I decided to centralize the logic into one. However, as a beginner programmer I have a few questions regarding it:
 
Note: I've been generating all networks from http://pages.ripco.net/~jgamble/nw.html
 
 
Parallelism:
 
Since the operations are all separated into parallels, is there any more optimal way of structuring the comparisons to make use of multithreading? My understanding is there is a time cost to the hardware switch between threads, and since these are generic low-cost comparisons I figured running the ifs in sequence would be faster anyway. But I'm a multithreading noob so if I'm wrong please correct me.
 
Sorting Network Optimization:
 
I've been struggling to find comprehensive information on sorting networks outside of dense university papers, though an old article I encountered seems pretty straightforward and definitive: http://www.drdobbs.com/sorting-networks/184402663
 
I'm already certain that Bose-Nelson networks are the most optimal option when n <= 8, but wasn't able to locate definitive information on larger sizes (and too lazy to test all the test cases right now). According the article linked above, there still are guaranteed optimal networks for 9 <= n <= 16 using non-BoseNelson algorithms. When Algorithm choice is "Best" on the generator I linked above(http://pages.ripco.net/~jgamble/nw.html) it provides a lighter version of its Bose-Nelson counterpart, which I am assuming is in fact more optimal than traditional algorithms.
 
I'm a bit less certain in the cases of 17 <= n <= 32. I'm assuming the larger it gets, the less distinct the advantage networks have over traditional algorithms. For that reason, I'm drawing the conclusion that they should only be used when array input order is entirely unknown and thus an appropriate algorithm can't be informedly-chosen. But I'm wondering if they have any use in this case, or if you're generally better off with any sorting algorithm? I'm planning running some test cases, but any expert input to help narrow criterea is welcome.
 
General Library Structure:
 
I'm less familiar with building libraries in C# compared to C++, so considering this is a single source file I figured the best method of distribution is just the source. But is it considered good practice to wrap it in a namespace and .dll file etc? It's obviously mostly for personal use, but considering it's an optimal solution for n <= 16 cases and it saves a lot of mindless legwork I figured it may as well be open source.
 
 
Apologies for the variety in questions, don't feel obligated to address every single one if you respond.

Share this post


Link to post
Share on other sites
Advertisement

I would think (not know) that, since you would have to synchronise the threads so often - e.g. 4 times in the Sort_8 case, relative to only doing 7 levels of comparison - that the overhead of multithreading would be a net cost more than a benefit. This may change if comparison itself is expensive - e.g. "which of these 2 remote websites has the most images on it?" - and where it's possible to effectively perform comparisons in parallel (which may not be true, even of the previous example, if retrieving the website saturates the single shared network connection).

 

Probably the simplest way to implement slow operations in parallel that need to synchronise at certain points is to use some sort of 'futures' system (https://msdn.microsoft.com/en-gb/library/ff963556.aspx). You can fire off 4 operations, wait for them all to complete, then move on to the next stage. If the futures are using a thread pool then the threading overheads can be fairly minimal. But again, the overhead of the mere extra code and functions is going to vastly outstrip the benefits if comparisons are cheap (e.g. strings, integers).

 

I'd be very surprised if this algorithm, multi-threaded or not, outperformed the standard sort algorithms provided by C#. Most standard library sort algorithms are optimised for special cases like small values of N, for example. When they say it's 'optimal' for N<16 that's referring to the number of comparisons, not the actual execution time. In fact I'd expect (again, my personal conjecture) execution on cheap comparisons to be poorer with this system because the code size is larger and there are more conditional statements, both of which are often culprits in high-performance code.

 

Regarding distribution, I like C# code to be in its own namespace, but beyond that I just like to get the plain source code. A unit test suite is also a good idea if you want to be taken seriously (i.e. executable proof that your sort returns the same results as a standard sort).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By 3dmodelerguy
      So I am building a turn based rogue-like (think CDDA). The game is going to have a very large map (up to 1000's x 1000's) however to alleviate most of that I obviously can't render everything so there will just be render a certain radius around the player and just load in and out data as the player moves.
      The next major system I am prototyping is making interactive tiles destructible and pretty much everything will be destructible besides basic landscape (cars, doors, windows, structures, etc. will be destructible)
      While I am only rendering a certain amount of tiles around the player, I want to keep the amount of colliders active at one time to be as small as possible for performance and currently the tilemap tool I use automatically merges colliders together.
      So instead of creating a separate colliders for each of these tiles and having the destructible behavior tied to that object (which my tilemap tool would allow me to do) I was thinking that I would store an array of all the X and Y locations for the interactive tilemap layer and let the tilemap manage the colliders. 
      Then when I hit a collider on the interactive tilemap layer, instead of of getting the behavior for how to deal with the destruction for that tile from that game object, I would pull it from the array I mentioned earlier based on the tile I attempt to interact with which I already have.
      Does this sound like a good approach? Any other recommendations would be welcomed.
    • By NDraskovic
      Hey guys,
      I have a really weird problem. I'm trying to get some data from a REST service. I'm using the following code:
       
      private void GetTheScores() { UnityWebRequest GetCommand = UnityWebRequest.Get(url); UnityWebRequestAsyncOperation operation = GetCommand.SendWebRequest(); if (!operation.webRequest.isNetworkError) { ResultsContainer rez = JsonUtility.FromJson<ResultsContainer>(operation.webRequest.downloadHandler.text); Debug.Log("Text: " + operation.webRequest.downloadHandler.text); } } The problem is that when I'm in Unity's editor, the request doesn't return anything (operation.webRequest.downloadHandler.text is empty, the Debug.Log command just prints "Text: "), but when I enter the debug mode and insert a breakpoint on that line, then it returns the text properly. Does anyone have an idea why is this happening?
      The real problem I'm trying to solve is that when I receive the text, I can't get the data from the JSON. The markup is really simple:
      [{"id":1,"name":"Player1"},{"id":2,"name":"Player2"}] and I have an object that should accept that data:
      [System.Serializable] public class ResultScript { public int id; public string name; } There is also a class that should accept the array of these objects (which the JSON is returning):
      [System.Serializable] public class ResultsContainer { public ResultScript[] results; } But when I run the code (in the debug mode, to get any result) I get an error: ArgumentException: JSON must represent an object type. I've googled it but none of the proposed solutions work for me.
      Also (regardless if I'm in the debug mode or not) when I try to do some string operations like removing or adding characters to the GET result, the functions return an empty string as a result
      Can you help me with any of these problems?
      Thank you
    • By nihitori
      The Emotional Music Vol. I pack focuses on beautiful and esoteric orchestral music, capable of creating truly emotive and intimate moods. It features detailed chamber strings, cello and piano as the main instruments, resulting in a subtle and elegant sound never before heard in video game royalty-free music assets.

      The pack includes 5 original tracks, as well as a total of 47 loops based on these tracks (long loops for simple use and short loops for custom / complex music layering).

      Unity Asset Store link: https://www.assetstore.unity3d.com/en/#!/content/107032
      Unreal Engine Marketplace link: https://www.unrealengine.com/marketplace/emotional-music-vol-i

      A 15 seconds preview of each main track is available on Soundcloud:
       
    • By RoKabium Games
      Another one of our new UI for #screenshotsaturday. This is the inventory screen for showing what animal fossils you have collected so far. #gamedev #indiedev #sama
    • By eldwin11929
      We're looking for programmers for our project.
      Our project is being made in Unity
      Requirements:
      -Skills in Unity
      -C#
      -Javascript
      -Node.js
      We're looking for programmers who can perform a variety of functions on our project.
      Project is a top-down hack-and-slash pvp dungeon-crawler like game. Game is entirely multiplayer based, using randomized dungeons, and a unique combat system with emphasis on gameplay.
      We have a GDD to work off of, and a Lead Programmer you would work under.
      Assignments may include:
      -Creating new scripts of varying degrees specific to the project (mostly server-side, but sometimes client-side)
      -Assembling already created monsters/characters with existing or non-existing code.
      -Creating VFX
      -Assembling already created environment models
      If interested, please contact: eldwin11929@yahoo.com
      This project is unpaid, but with royalties.
       
      ---
      Additional Project Info:
      Summary:
      Bassetune Reapers is a Player-verus-Player, competitive dungeon crawler. This basically takes on aspects of dungeon crawling, but with a more aggressive setting. Players will have the option to play as the "dungeon-crawlers" (called the 'Knights', or "Knight Class", in-game) or as the "dungeon" itself (literally called the 'Bosses', or "Boss Class", in-game). What this means is that players can choose to play as the people invading the dungeon, or as the dungeon-holders themselves.
      Key Features:
      -Intense, fast-paced combat
      -Multiple skills, weapons, and ways to play the game
      -Tons of different Bosses, Minibosses, creatures and traps to utilize throughout the dungeon
      -Multiple unique environments
      -Interesting, detailed lore behind both the game and world
      -Intricate RPG system
      -Ladder and ranking system
      -Lots of customization for both classes s of customization for both classes
  • Advertisement