Sign in to follow this  
cmac

Unity Implementing a C# Sorting Network Library

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

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Announcements

  • Forum Statistics

    • Total Topics
      628298
    • Total Posts
      2981890
  • Similar Content

    • By CpawsMusic
      Hey there! My name is Cpaws and I compose music, sound effects and overall sound design for video games and film. I'm looking to work on a horror game mainly for fun and as an addition to my portfolio. I've used Unity & Wwise before for audio implementation.
      If you're interested in working together, don't hesitate to contact me at cpawsmusic@gmail.com
      Here's a few demo reels of my past projects: 
      Here's some snippets of some quick game music I've composed: https://soundcloud.com/cpawsmusic/sets/cpaws-video-game-film-music
      Here's my portfolio/website: https://CpawsMusic.com/
      E-mail: cpawsmusic@gmail.com
    • By muhamad rabee
      My first mobile game made by unity

      iphone: https://itunes.apple.com/us/app/aa-countdown/id1314223584?ls=1&mt=8

      android: https://play.google.com/store/apps/details?id=com.mr.AACountDown

      I appreciate every suggestion
    • By Simplepg
      https://play.google.com/store/apps/details?id=simple.gplay.GamesInABox
    • By Simplepg
      https://play.google.com/store/apps/details?id=simple.gplay.GamesInABox
    • By ForgedInteractive


      Who We Are
      We are Forged Interactive, a small team of like-minded game developers with the sole purpose of making games we love! We're a team of artists, animators, programmers, level designers, writers, composers, producers, and other creative minds. We want to make games that you, the modern gamer want to play! We hope to build a community that enjoys our games as much as we love creating them. With your feedback and support we will be able to achieve that.

      About the Game
      GAME NAME is a fun, action-packed army builder with unique characters, challenges and engaging levels. Set forth on an adventure to protect friends, family and countrymen from new adversaries. Once defeated your enemies turn coat and join you in your adventures. Players can enjoy a range of troops and abilities based on their gameplay style which become more important as maps introduce more challenging terrain, enemies and bosses. Strong orc knights, dangerous shamans, and even a dragon are out on the prowl. Knowing when to fight and when to run, and how to manage your army is essential. Your actions alone decide the fate of this world.

      Previous Work by Team
      Although we are working towards our first game as a team, our team members themselves have past experience in the industry.
      This includes members who have worked on titles including:
      Final Fantasy Kingsglaive, FIFA, Xcom 2 and Civilization.

      Who are we looking for? 3D Modellers Concept Artists Marketing Specialists Level Designer

      What do we expect? Reference work or portfolio. Examples what have you already done and what projects you have worked on academic or otherwise. The ability to commit to the project on a regular basis. If you are going on a two-week trip, we don't mind, but it would be good if you could commit 10+ hours to the project each week. Willingness to work with a royalty based compensation model, you will be paid when the game launches. Openness to learning new tools and techniques
      What can we offer? Continuous support and availability from our side. You have the ability to give design input, and creative say in the development of the game. Shown in credits on websites, in-game and more. Insight and contacts from within the Industry.
      Contact
      If you are interested in knowing more or joining. Please email or PM us on Skype. Myself or Colin will reply to you within 48 hours.

      E-mail: Recruitment@ForgedInteractive.com
      Skype: ForgedInteractive

      Regards,
      David and Colin

      Follow us on:

      Facebook: https://www.facebook.com/ForgedInteractive/
      Twitter: @ForgedInteract
      Youtube: https://www.youtube.com/channel/UCpK..._as=subscriber
      Reddit: https://www.reddit.com/user/Forged_Interactive/
  • Popular Now