JASS Challenge

Heh, this is a rather cheap solution and we already considered it, that was a part of the "stack rooms in 1 array" solution, but it has some cons. But yeah, you can raise that limit though. I even heard it works in multiplayer (importing common.j with a edited array-limit-constant)

Cubasis

I thought it was some technical reason that did not allow for larger arrays. Have you actually tested that? The constant defined in common.j is just a constant for use in scripts and it would be the only constant that would have any effect without actually being passed to a native. Well, I'll run some tests myself and look what happens when you use larger arrays.

@Cubasis40: I check my PMs. I just looked and I could not see any PM from you. Maybe you somehow sent it to the wrong person or it got lost. Well, resend it or send it to my email ([email protected]) Although that is not very reliable either it seems. The submission from Epigoni took 2 days before it finally arrived.

Took a day and a half for your e-mail to reply telling me my first e-mail didn't make it through. =)

I knew that (mostly because I saw your sinergies map) but I just thought that with the heap functions I would be able to make things like

function Create2Darray takes integer xmax, integer ymax returns integer

function Set2Darrayvalue takes integer D2array, integer x, integer y, integer value returns nothing

function Get2Darrayvalue takes integer D2array, integer x, integer y returns integer

just an idea though

I'm considering making a Heap, I'm currently doing a tournament version of a heap implemented with an array as part of a large externalized dijkstra graph search.

So... there isn't anything wrong with doing the tournament version of the heap (it still works the same way)?

EDIT: Also that interface blows. All a heap has to do is insert(object, priority) and deleteMin() in O(logn) time. Everything else is just gravy.

EDIT EDIT: Ah oki. :)

What is meant here is not a priority heap. Instead it means the part of memory of a program that is called the heap. The part where you can reserve memory during the run of the program and free it again some time. The objective of the challenge is to create the functions that handle the heap.

Lord Vexorian it might be possible but I don't really see that as anyeasier then just going
set Value{Index(x,y)]=Value

As far as ylimit its true I ussually leave it static, but it could easily be an integer variable, the advantage can sort of be seen that the x axis is limitless...

For 2d arrays a simple index (In some of my more lazier maps I make the function Ix because its shorter) function will most likely always be easiest. For higher dimensions I'm not sure.

Up to now I only got submissions from Peppar and TheEpigoni. But since in the case of TheEpigoni the email got delayed it might have been the same with another submission. I will post the winners sunday afternoon (european time) and what does arrive until then is in.

The JASS challenge number one is over.
There have been two submissions and the winner is Peppar.

The pot is at 255 points. Peppar gets 170 and TheEpigoni 85.
You have time until monday afternoon (european time) to state things I overlooked or you do not agree with. After that I will transfer the points.

The maps with the implementations are attached to the post.

Here is an analysis of the implementations (including the reference implementation of the heap I made):

Peppars implementation of the heap

The way it works:
It stores the information about the allocations in a sorted allocation list. For HeapNew it searches through that list to find a free space of sufficient length in between the allocations and then enters the new allocation at that point in the list.
For HeapDelete it searches the allocation list for the right allocation and then removes it from the list.

Of course this list has to be implemented on a kind of heap structure itself. In this case it has constant allocation lengths. This descriptor array is searched for a free space now field by field in a ring fashion. That means it will start not start at the beginning but at the point it stopped last time. So you have a long time of constant runtime of this until the entire 2 descriptor arrays have been used up and then he starts with the search at the beginning again.

Efficiency analysis of the functions:
LowWord: O(1)
HighWord: O(1)
CreateDWord: O(1)
SetLowWord: O(1)
SetHighWord: O(1)
HeapGet: O(1)
HeapSet: O(1)
HeapDescriptorArrayGet: O(1)
HeapDescriptorArraySet: O(1)
HeapDescriptorGet: O(1)
HeapDescriptorSet: O(1)
IsHeapDescriptorFree: O(1)
HeapFindFirstFreeDescriptor: O(Distance on Descriptor array from alloc cursor to free one)
HeapMergeNewDescriptor: O(Distance on Descriptor array from alloc cursor to free one)
HeapNew: O(max(number of allocations until free space on heap, Distance on Descriptor array from alloc cursor to free one))
HeapDescriptorFind: O(Number of Allocations until the one to be found)
HeapDescriptorClear: O(1)
HeapDescriptorDelete: O(1)
HeapDeleteEx: O(Number of Allocations until the one to be found)
HeapDelete: same as HeapDeleteEx
Since the Distance on Descriptor array from alloc cursor is 1 for a long time, the relevant number for HeapNew is the number of allocations on the heap until the free space is found. Unfortunately that can be pretty long if there are many small allocations that are not deleted. Maybe saving some information from previous searches can improve that (so he does not search through large parts without any free space in between the allocations).
The problem with HeapDelete is that its worst case O(Length of Allocation List) happens very often when the HeapNew and HeapDelete happen stack-like (as they often do in programs when subprograms allocate, then compute something calling other subprograms and then disallocate before returning to main program or the subprogram that called it). To improve that I suggest searching the allocation list from back to front instead of front to back (since it is double linked that is easy). Of course that is completely heuristic and for both ways there are examples where they are superior to the other.

Advantages:
- The length of the allocation to delete does not need to be passed to HeapDelete
- Fast if there are large allocations

Disadvantages:
- HeapDelete runtime is not constant, especially slow for allocations and disallocations in a stack-like fashion
- Many variables that need to be copied to use it

Peppars implementation of the list:

It is pretty much the list I had in mind when I made that specification with two useful functions added. So I have not much to say about it.

Points:
Utility: 10
Efficiency: 8
Maintainability / Extendability / Reusability: 8
Bonus: 5
Total: 31


TheEpigonis implementation of the heap

The way it works:
It stores the information which fields of the array are used in a separate boolean array. This array is searched from the beginning until an unused space of sufficient size is found. HeapDelete is done by setting the used fields to false again.

Efficiency analysis of the functions:
HeapGet: O(1)
HeapSet: O(1)
HeapNew: O(Distance on the usage array from beginning to area of sufficient size)
HeapDelete: O(length of allocation)
The problem with HeapNew is that it takes a long time when you first allocate one large block and then many small ones as it depends on how far back in the heap the free space is.

Advantages:
- Fast if there are very many small allocations and a high degree of fragmentation
- Few variables (2 arrays) to be copied to use it
- HeapDelete is nearly constant (for small allocations)

Disadvantages:
- HeapNew takes a long time with large allocations
- HeapDelete is non constant for large allocations
- Multiple arrays for larger memory where not implemented (although it is quite possible to extend the implementation for that)

TheEpigonis implementation of the list:

There are 2 things I do not like about this implementation.
First ListAddItem adds the item at the end of the list. This is usually a bad idea with lists unless you have a pointer to the tail as it costs O(length of the list) time to reach that end. It is much better to add at the head as you have only constant cost there.
Second the chosen null pointer as 9999 is in a range that can easily be reached when the memory is extended. Of course that is easily fixable.

Points:
Utility: 6
Efficiency: 6
Maintainability / Extendability / Reusability: 6
Bonus: 3
Total: 21


Reference implementation of the heap

The way it works:
It connects the free spaces with a free list that is put in those free spaces themselves. For that the length of the free space and the pointer to the next free space is contained in one integer that is put at the beginning of the free space. The list is organized as a ring list. The anchor is stored in position 0 of the heap. This anchor wanders around the ring so it is not always searched from the same position (which would cause small free spaces to accumulate at the beginning).

Efficiency analysis of the functions:
HeapGet: O(1)
HeapSet: O(1)
HeapNew: O(distance on free list from anchor to free space with sufficient length)
HeapDelete: O(1)
Since the deleted space can be put in the free list at any position, HeapDelete has only constant cost. The main problem with that is that free spaces next to each other not joined. This causes an additional fragmentation effect. That can be countered by running a service every so often that marks the free spaces on a boolean array and creates a new free list from that.

Advantages:
- HeapDelete has constant cost
- HeapNew takes as maximum as long as the length of the free list which only grows with HeapDelete and not with HeapNew
- Only the heap array variables need to be copied to use it

Disadvantages:
- Additional fragmentation effect

In order to be useful to everyone we should maybe have all the usable functions listed and commented
Describe what the a scripter can do with those functions, maybe an example or something....

Thats a good idea. I will do so when I get back home this evening.

Well, took me a bit longer. But here is a small guide on how to use the heap and the list:

The Heap:

What can I do with the heap?
The heap can be used to store structs, arrays and other objects. They are then represented by a pointer, which is a simple integer that can be passed to and returned from functions, stored in the custom value of a unit or stored in another object on the heap.
That can also be used to store information in pointered data structures like lists, trees and graphs.

How can I start an object on the heap?
First you need to determine how much space your object will need on the heap. For example if you want to store an array of 30 integers on the heap then the space you will need is 30.
Then you reserve that space on the heap:
set p = HeapNew(length)
In the case of the example you would use HeapNew(30).
p needs to be an integer variable where you want to store the pointer to the heap object in.
Note: The object on the heap could now contain any values, it is not initialized with 0.

How can I access the object on the heap?
You access the object on the heap with pointers. The most important pointer is the one returned by HeapNew. It points to the start of your object. If you add one to that pointer, you will get a pointer that points to the second integer of your pointer. Be careful, not to access pointers beyond the range you reserved. So in the example do not access p+30, as this does not lie within the range you reserved and you could overwrite other data.
To access pointers you use HeapGet and HeapSet (this is usually called dereferencing a pointer). HeapGet returns the value a pointer points to, HeapSet changes that value.
So to retrieve the 5th integer of your object and store it in x you do:
set x = HeapGet(p+4)
To set the first value to 5 you do:
call HeapSet(p, 5)

How can I free the memory that an object uses?
To free the memory of an object when you don't need an object any more use:
call HeapDelete(p, length)
Be careful that you do not access the object any more after you deleted it.

How can I store that a pointer points nowhere?
That is what the 0-pointer is for. It is a special pointer value that HeapNew will never return. So do not access it.
set p = 0
Usually you will use that to mark the ends of pointered data structures.

How do I store data types other than integer in the heap?
For strings you will need a string heap. For all other data types you can use the return bug. With this you can convert these data types into an integer representation and vice versa (not sure if that works with strings and I think code does not work either). The conversion functions look like this:

function Real2Int takes real r returns integer
if r != 0.0 then
return r
endif
return 0
endfunction

Now to store a real r in the heap you use:
call HeapSet(p, Real2Int(r))
To retrieve it you use:
set r = Int2Real(HeapGet(p))


The List:

What can I do with the list?
If you store arrays on the heap you have to specify how long they should be max when you create them.
Lists are containers that do not have that problem, you can always add more items to them (unless you run out of memory). The disadvantage you get is that you cannot easily access items in the middle or at the end of the list. You have to go through them from the beginning to the end.

How can I create a list?
set l = ListNew()
Note that Peppars implementation of the list treats the 0-pointer as an empty list.

How can I add items to the list?
set l = ListAddItem(l, i)
This adds the item i to the beginning of the list.

How can I go through a list to retrieve or do something with items?
local integer p = l
loop
exitwhen ListIsEmpty(p)
...do something with the node p using ListGetHead(p) and ListSetHead(p, i)...
set p = ListGetNext(p)
endloop
This goes through the list l and allows you to do something with each node p.

How can I delete the first item in the list?
set l = ListDeleteHead(l)

How can I delete an item that is not the first one?
Go through the list to the node before the item you want to delete so that this node is stored in p now.
call ListSetNext(p, ListDeleteHead(ListGetNext(p)))

I can't believe I didn't know about this until now :P

So were Peppar and Epigoni's systems merged or what? I noticed that in your FAQ HeapDelete requires the length to be passed and in Epigoni's you mention that in his system you don't. If you just went straight with either one, why not synthesize the strong sides of both and make an uber heap api? ;)

It is Peppars implementation in which you don't need to pass the length to HeapDelete.
I recommend either the usage of Peppars implementation (especially if you have use of the easier HeapDelete) or the reference heap (especially if you have many small allocations) as TheEpigonis implementation is comparably slow, especially with large allocations.
Neither of the implementations is mergable as they all store the information in different ways.

In the reference implementation, try storing the list of free spaces as a binary tree. This would make allocation faster. If you make the minimum allocation length 2 integers or more, you can store some additional information as well.

Add a boolean array that stores if a block is free or not and you can implement a merging algorithm as well. These additions might make the reference implementation the best of the three.

There's an article on gamasutra.com from a programmer on the Rayman GBA team that talks about a few different memory allocation ideas, similar to andy's implementation. Only it was a year ago when I read the article :P