search

chapel-lang / chapel

a Productive Parallel Programming Language
https://chapel-lang.org
Other
1.79k stars 421 forks source link

How do users of radix sort specify what to sort by? #10599

Closed mppf closed 5 years ago

mppf commented 6 years ago

Unlike a comparison sort, a general radix sort doesn't have as obvious an interface. Where comparison sorts can request the user provide a comparison routine, radix sorts will need other information.

This issue is to discuss API design for radix sort including surveying what other implementations do.

mppf commented 6 years ago

What implementations do I know about?

LouisJenkinsCS commented 6 years ago

What about using the Comparator.key() method and have it return something that it is sortable by? That way if you call radixSort(arrayOfObjects) and then isSorted(arrayOfObjects) it should return true.

Using the example I see for the kxsort, can we overload key() to also have a specific method like Comparator.key(k) that gets the byte at index k? If we're sorting string objects, Comparator.key(k) can yield the character (although unicode may get a bit tricky), and if its a custom struct, they can have a method that handles calculating which field and byte into that field to extract the kth byte from. That way we can avoid having a specific interface for radix sort.

e-kayrakli commented 6 years ago

What about using the Comparator.key() method and have it return something that it is sortable by? That way if you call radixSort(arrayOfObjects) and then isSorted(arrayOfObjects) it should return true.

Although I agree that this is the most obvious way to have the needed functionality, it might be confusing to have something named "Comparator" being passed to a non-comparison sort.

Maybe, something similar to RadixTraits in the kxsort example above and the Comparator interface in Chapel can be unified in a simple class hierarchy. Where the default key method (in a parent class) returns the argument directly and the default compare (in a child class) uses <. The programmer, then, can inherit these base classes with appropriate overrides. Using classes instead of records might complicate things, though. Especially when you use distributed memory.

LouisJenkinsCS commented 6 years ago

Maybe, something similar to RadixTraits in the kxsort example above and the Comparator interface in Chapel can be unified in a simple class hierarchy.

I'm not sure if I like having to allocate a class object on the heap just to be used one time as a comparator (since record inheritance has been removed from the language from PRs revolving around issue #6851), and as you said it complicates things from the perspective of distributed memory. Really I'm in favor of a short-term temporary solution, as who knows when traits and interfaces will be implemented.

One other solution I can think of is forcing the user to define methods for the types they want to use...

proc string.byte(k) {
   return ascii(this[k]);
}

TIO

mppf commented 6 years ago

What about using the Comparator.key() method and have it return something that it is sortable by? That way if you call radixSort(arrayOfObjects) and then isSorted(arrayOfObjects) it should return true.

Although I agree that this is the most obvious way to have the needed functionality, it might be confusing to have something named "Comparator" being passed to a non-comparison sort.

In my previous project where I created such an API, I called it the sorting "Criterion". We could do the same here. However note that many radix sorts will fall back on comparison sorting, and additionally sometimes having the comparator there is useful for doing additional work when all of the key bytes compare the same. So I'd prefer a combined interface - and in that setting, calling it Criterion or Comparator would be OK with me.

Note that the term "comparator" in the sort module is all about documentation and not enforced by the compiler. (Well, that's mostly true; there is the one exception of named argument passing, e.g. sort(comparator=myThing)). So, we could change the documentation to call it "Criterion" or even use different terms for radix sorts. The code is the same (it just tries to find the appropriate methods in the passed record).

Regarding Comparator.key() and Comparator.key(k), that would be fine, but we'd still need to have a way to indicate how long each key is. That comes up in sorting strings of unequal length.

LouisJenkinsCS commented 6 years ago

Regarding Comparator.key() and Comparator.key(k), that would be fine, but we'd still need to have a way to indicate how long each key is. That comes up in sorting strings of unequal length.

Well besides for straight-forward solution of forcing the user to fill out another method (I.E Comparator.numBytes(elt : eltType)), I'm wondering if we can just have the user return all bytes of the object and then cache that in an on-demand way for objects to avoid having to querying the k'th byte each time.

proc Comparator.bytes(elt : eltType) : ByteBuffer {...}

// in implementation...
var byteMapDom : domain(eltType);
var byteMap : [byteMapDom] ByteBuffer;

// When want to compare two objects...
if byteMap[e1].size == byteMap[e2].size then // ..

// When you want to compare individual bytes...
const e1Byte = byteMap[e1][k]
const e2Byte = byteMap[e2][k];

It is a bit heavy-handed but its really only needed for larger arrays of data.

avneetreen commented 6 years ago

Here are some libraries which implement radix sort, that I came across, which can be referred to:

Its mentioned in stackoverflow discussions, that Thrust uses radix sort for sorting integers. (https://stackoverflow.com/questions/45267748/which-sorting-algorithm-used-in-thrustsort)

mppf commented 6 years ago

Here are some libraries which implement radix sort, that I came across, which can be referred to:

Its mentioned in stackoverflow discussions, that Thrust uses radix sort for sorting integers. (https://stackoverflow.com/questions/45267748/which-sorting-algorithm-used-in-thrustsort)

The sorting "by key" is one strategy we could consider: https://thrust.github.io/doc/group__sorting.html#ga2bb765aeef19f6a04ca8b8ba11efff24 -- here the sort function is provided with two C++ iterators; one is to the keys and another is to the values. I'm not so confident that this will work with Chapel though, because Chapel iterators are much more than just pointers. I think the nearest thing would be to implement Radix sort taking two arrays, where one is the keys and the other is the values. This is too space-inefficient for my taste though.

Besides taking in separate keys and values, this one is effectively has an interface like "Tell me which bits of the data are key bits". The problem with that is that some Chapel types (e.g. string) logically contain data but in practice point to that data. So that doesn't seem general enough to me.

This one seems really similar to the CUB case in terms of interface.

LouisJenkinsCS commented 6 years ago

Besides taking in separate keys and values, this one is effectively has an interface like "Tell me which bits of the data are key bits". The problem with that is that some Chapel types (e.g. string) logically contain data but in practice point to that data. So that doesn't seem general enough to me.

Can we possibly create a default way of obtaining the key for primitive types, and then allow the user to recursively obtain the key for each field and combine them together? This is based on the assumption that eventually all data types are composed of primitives...

class C {
   var x : int;
   var y : real;
   var z : (string, otherClass); 
}
proc C.bytes(buf : ByteBuffer) {
   x.bytes(buf);
   y.bytes(buf);
   // Tuple calls on each element it is composed of
   z.bytes(buf); 
}

That seems relatively painless. The compiler can even generate something like this for most types. bytes(buf) can append data to the ByteBuffer.

mppf commented 6 years ago

proc Comparator.bytes(elt : eltType) : ByteBuffer {...}

I'm not really in to this approach because:

Regarding the endianness issue, x86 and most CPU architectures are little endian. That means that if you take a pointer to an int and then read it 1 byte at a time, you'll get the least-significant digits first. E.g. for an uint(32), 0x01020304, if you dump the bytes from memory, you'd get 0x04, 0x03, 0x02, 0x01. So it would sort wrong. (And it's not so easy to just swizzle every 4 bytes, since you wouldn't want to do that to a string, e.g.).

So, I think components of a good solution here are:

LouisJenkinsCS commented 6 years ago

it adds a new type (ByteBuffer)

We can reuse Buffers.buffer if this is an issue.

that type will necessarily alias other things in a way that is weird in Chapel (i.e. it's C pointer)

A c_ptr(eltType) can possibly dereference the pointer to obtain bytes from eltType, although maybe I am misunderstanding this one.

I'd like the radix sorting to reasonably handle integer keys on platforms with different endianness.

If we're going with the whole 'primitives implement bytes(buf : ByteBuffer) then those can handle endian-ness for each type. If we have int.bytes(buf : ByteBuffer), it can handle pushing/appending its bytes in reverse order.

mppf commented 6 years ago

If we're going with the whole 'primitives implement bytes(buf : ByteBuffer) then those can handle endian-ness for each type. If we have int.bytes(buf : ByteBuffer), it can handle pushing/appending its bytes in reverse order.

The thing getting a key / part of a key is like a comparison routine in a comparison sort. It'll be called many many times in the sort kernel. If it's appending data to a buffer, that puts the memory allocator (and other complexity) in the kernel. I think this would be really bad for sort performance.

mppf commented 6 years ago

Here is one sketch of Comparator options:

First, a key method. This is already supported by the Sort module. I think it's important to continue supporting it because:

record KeyComparator {
  proc key(sortedElement) {
    /* returns the key to use when sorting;
        key needs to be a type supported by
        the sort library. Hopefully that includes
        all the numeric types as well as string. */
    return sortedElement.integerField; // an example
  }
}

Next, a way to get part of a key (in case it is long) for radix sorting. This supports sorting variable-length elements (such as strings or bigints). This is how the library can implement a key method returning a string.

I see two options here.

Option 1: comparator works bits-at-a-time:

record KeyBitsComparator {
  proc keyBits(sortedElement, startbit: int):(uint,bool) {
    /* returns the part of the key starting at startbit.
        The radix sort routine assumes all of the returned
        bits are relevant but this routine can put 0s in any
        lower-order bits that are unused. It returns also
        whether or not this key marks the end.*/
    // for example, if the key were just  1 8-bit value, it would return:
    if startbit < 8  {
      var bits:uint = 0;
      bits = sortedElement.byteValue;
      bits <<= startbit;
      return (bits, false);
    } else return (0, true);
  }
}

Option 2: comparator works a "part" at a time, where that the "part" can be any numeric type:

record KeyPartComparator {
  proc keyPart(sortedElement, start: int):(uint(?),bool) {
    /* returns the part of the key starting at part number `start`.
        It returns also whether or not this key marks the end.*/
    // for example, if the key were just 1 8-bit value, it would return:
    if start == 0 then return (sortedElement.byteValue, false);
    else return (0, true);
  }
}

I see one other dimension of possibility; instead of returning tuples with a "done" indicator, there could be a separate method to query the number of bits / parts in the key.

ben-albrecht commented 6 years ago

I am liking the KeyComparator.key() approach due to its simplicity and consistency with the existing Sort module.

As for the 2nd method of getting part of a key, I am leaning toward KeyPartComparator.keyPart() (option 2) mostly because the framework and implementation seems easier to understand and thus easier for a user to write, assuming the examples provided are representative of what a user would typically write.

A few thoughts on this approach:

mppf commented 6 years ago

Could keyPart (or keyBits) just be an additional method on KeyComparator such that the user only needs to construct one comparator record to pass into the sort routine?

That's what I was expecting to happen.

In the long-term, we'd like for the Sort module to support first class functions (when #8351 is resolved) in addition to these comparator records (less verbose, similar to other sorting interfaces, etc.) We should keep this in mind for the radixSort interface. For example, comparator.key() and comparator.keyPart() could become 2 separate arguments to the FCF interface for radixSort.

It seems we could easily add new FCF overloads of sort/radixSort and then have them construct an appropriate Comparator.

avneetreen commented 6 years ago

The key method of comparator seems fine to me. For the second case, when we have to get a part of the key, from what I understand (Correct me If I’m wrong) the keyBits extracts any chunk or any number of bits from the key starting from the start bit, whereas the part key (Option 2) extracts 8 bit chunk in the entire key starting from the start bit. The second one indeed is simple to understand and we could start with that.

mppf commented 6 years ago

The idea is that the keyPart method could return an integer size of its choice (maybe 8 bits or maybe 64 bits, depending).

the keyBits extracts any chunk or any number of bits from the key starting from the start bit,

yes

the part key (Option 2) extracts 8 bit chunk in the entire key starting from the start bit

it's meant to allow other integer types too, e.g. 16-bit or 64-bit integers