Jump to content


Photo

Fast Priority Queues


  • Please log in to reply
8 replies to this topic

#1 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 17 March 2011 - 10:45 PM

>>Download<<
(134 KB)

ABOUT
Others have done things like it. Noone has done it as well. This is a complete O(log n) priority queue to replace GM's O(n) queue. Every function for Game Maker's priority queue is implemented, and a function to merge two queues has been added.

Please note that the FDS queues begin beating the DS queues only when they contain sufficiently many elements. Here is experimental data on what "sufficiently many elements" means for various GM versions and extensions.
  • GM:8.1, DLL extension, direct-access functions: 23 elements
  • GM:8.1, DLL extension, generalized functions: 93 elements
  • GM:8.1, GML extension: 1024 elements
  • GM:Studio, DLL extension, direct-access functions: 64 elements
  • GM:Studio, DLL extension, generalized functions: 296 elements
  • GM:Studio, GML extension: 8200 elements
All functions tested ran faster - up to 3x in the case of the GML extension - in GM:Studio than in GM:8.1, but Studio's priority queues are also faster than their GM:8.1 equivalents.

HOW
Version 2.2 and the GML implementation use a binary min-max heap.
The DLL and dylib in Versions 2.3 and 2.4 use a double-heap, which reduces the average number of comparisons during removals.

Version 2.5 uses an interval heap, which improves on the concept of a double-heap by reducing paged memory access.

FUNCTIONS
Replacements for all of Game Maker's ds_priority functions:
Spoiler

Additions for greater ease of use:
Spoiler

Additions for greater efficiency (Call these directly to avoid GM's script overhead):
Spoiler


VERSION HISTORY
  • 2.5 - Improved C++ performance and reduced memory consumption, created GML extension using interval heap, removed deprecated functions and dylib, and moved to different licence.
  • 2.4 - Rare bug fixed, improved C++ source, updated unregistered GML version, created more sensible naming scheme for exported DLL functions, created more sensible naming scheme for GM functions, and deprecated (but not removed) old naming scheme.
  • 2.3 - HAS ERROR Reworked DLL back-end. Now has better average performance for large queues. Small-queue performance not noticeably changed. Additionally adds an untested dylib. Error Description: Removing minimum element from queue of 2 elements removes incorrect element.
    2.2 - Reduced memory use for numbers. Performance is unchanged.
  • 2.1 - OBSOLETE Slight tweaks, source code released.
  • 2.0 - OBSOLETE Reworked entire back end. Now is much more useful. Also doubled maximum size of unregistered queues and fixed bugs.
  • 1.1 - OBSOLETE Updated to work with both 8.1 and 7.0. fds_priority_read reads strings from both, and fds_priority_write writes for 7.0 (which 8.1 can read)
  • 1.0 - OBSOLETE Release
Tools

Edited by Gamer3D, 21 November 2013 - 05:51 AM.

  • 2

#2 brac37

brac37

    GMC Member

  • GMC Member
  • 808 posts
  • Version:GM7

Posted 18 March 2011 - 07:23 PM

I can find min heaps and max heaps on Wikipedia, but no min-max heaps. Perhaps you did it like this. Nice job. Or should I say, poor job from GameMaker?

Now that your scripts are so incredibly fast, you can slow them down by adding median support. You use two heaps, one for the lower half and one for the upper half. These heaps can be interlaced and followed by the actual median (when the count is odd).
  • 0

#3 LSnK

LSnK

    NaN

  • GMC Member
  • 1188 posts

Posted 22 March 2011 - 02:28 AM

Nice work. Thanks for going all the way with the idea.
  • 0

#4 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 22 March 2011 - 02:54 AM

Now that your scripts are so incredibly fast, you can slow them down by adding median support. You use two heaps, one for the lower half and one for the upper half. These heaps can be interlaced and followed by the actual median (when the count is odd).

Not going to separate it into two heaps. This extension is primarily a fast alternative to the ds_priority functions. The min-max-median heap would be at least O(log n) for both finding and popping the minimum/maximum, while the min-max heap is O(1) for finding. I will look into the possibility of adding peek/pop median support, but if I don't find a good algorithm, it's not going in there. Current best algorithm found: O(n log n)

Nice work. Thanks for going all the way with the idea.

You're welcome. And thanks for pointing out the problem. Without your topic, I'd have assumed that GM's structures were efficient. The most annoying part was replicating ds_priority_read.

Hmm... Now that I think about it, I remember hearing something about GM storing strings even after they've been set to reals. I'll update it again with failsafes to make sure it works with this.

EDIT: Update added. It should now have no problems reading real numbers which used to be strings (Even if it did before).

Edited by Gamer3D, 22 March 2011 - 08:59 PM.

  • 0
Fast Priority Queues - Game Maker's priority queues are O(n). Mine do everything that Game Maker's do, but in O(log n) time.
Dual-Quaternion Skinning - Modifying vertexes in GM is slow. This simple vertex shader does the job both quickly and well.

#5 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 16 April 2011 - 09:17 PM

Now that GM8.1 is out, I have updated my scripts to be compatible with it. The main change with the latest version is that fds_priority_read needs to be compatible with it.

Edited by Gamer3D, 23 April 2011 - 07:11 AM.

  • 0
Fast Priority Queues - Game Maker's priority queues are O(n). Mine do everything that Game Maker's do, but in O(log n) time.
Dual-Quaternion Skinning - Modifying vertexes in GM is slow. This simple vertex shader does the job both quickly and well.

#6 PoniesForPeace

PoniesForPeace

    puzzling

  • GMC Member
  • 494 posts
  • Version:GM:Studio

Posted 08 July 2012 - 06:09 PM

Thanks, I may use this with Pad3D when I get the time.
  • 0

PoniesForPeace is back baby!   :thumbsup:


#7 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 24 December 2012 - 03:17 AM

There's a new DLL back-end (reduces comparisons, especially when popping elements). I've also added a dylib for Mac uses.

That said, I need testers. I changed some compiler settings, and I need people to try the DLL or the extension to see if I managed to fully remove the dependencies on shared libraries. I also need Mac testers.

Here's my add/delete benchmark program. It displays the relative time required for built-in ds_priority_ (blue line) and the extension's fds_priority_ (green line). These times are based on 10000 repetitions of priority_add and priority_delete_max, maintaining n elements in the queue (for the extension, the direct calls are used).
My results are:
  • Extension surpasses built-in at n=24 elements.
  • GML surpasses at approximately n=1024 elements.
  • DLL only benchmarked through extension.
  • Dylib untested.

  • 0
Fast Priority Queues - Game Maker's priority queues are O(n). Mine do everything that Game Maker's do, but in O(log n) time.
Dual-Quaternion Skinning - Modifying vertexes in GM is slow. This simple vertex shader does the job both quickly and well.

#8 Nediradesigns

Nediradesigns

    GMC Member

  • GMC Member
  • 97 posts
  • Version:GM:Studio

Posted 10 May 2013 - 02:39 PM

I wouldnt mind testing (I have studio and have mac and windows computers) however unsure of how to really use this for the games/apps I am developing 


  • 0

#9 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 12 May 2013 - 03:39 AM

I wouldnt mind testing (I have studio and have mac and windows computers) however unsure of how to really use this for the games/apps I am developing 

Excellent. Just run a program (any program) that uses the extension on a Mac. If a couple of functions work, it's quite likely that all of them do.

 

It's intended as a replacement for a relatively slow part of GM, not as something to build a game around. If you use ds_priority for something, you can use fds_priority in the same way for a handy speed-boost. The more elements you keep in your priority queues, the bigger the speed boost from switching.


  • 0
Fast Priority Queues - Game Maker's priority queues are O(n). Mine do everything that Game Maker's do, but in O(log n) time.
Dual-Quaternion Skinning - Modifying vertexes in GM is slow. This simple vertex shader does the job both quickly and well.