Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unification of int, empty array and int array fails #12

Closed
asterite opened this issue Jan 22, 2013 · 1 comment
Closed

Unification of int, empty array and int array fails #12

asterite opened this issue Jan 22, 2013 · 1 comment

Comments

@asterite
Copy link
Member

a = 1
a = []
a = []
a << 1

"a" is incorrectly typed as a union of Int and Array<Int>, but it should be a union of Int, Array<Nil> and Array<Int>

asterite pushed a commit that referenced this issue Jan 22, 2013
@asterite
Copy link
Member Author

Simpler test case:

class Int
  def value=(x)
  end
end

a = 1
a = Pointer.malloc(1)
a.value = 1
a = Pointer.malloc(1)

It's simpler because it doesn't involve arrays.

And another one with just objects:

generic class Foo
  def value=(value)
    @value = value
  end
end

foo = Foo.new
foo.value = 1
foo = Foo.new

Should be union of Foo<> and Foo<Int> but it's just Foo<Int>

straight-shoota added a commit that referenced this issue Nov 26, 2024
Related to [RFC #12](crystal-lang/rfcs#12).

Replaces the `Deque` used in #14996 for a min [Pairing Heap] which is a kind of [Mergeable Heap] and is one of the best performing heap in practical tests when arbitrary deletions are required (think cancelling a timeout), otherwise a D-ary Heap (e.g. 4-heap) will usually perform better. See the [A Nearly-Tight Analysis of Multipass Pairing Heaps](https://epubs.siam.org/doi/epdf/10.1137/1.9781611973068.52) paper or the Wikipedia page for more details.

The implementation itself is based on the [Pairing Heaps: Experiments and Analysis](https://dl.acm.org/doi/pdf/10.1145/214748.214759) paper, and merely implements a recursive twopass algorithm (the auxiliary twopass might perform even better). The `Crystal::PointerPairingList(T)` type is generic and relies on intrusive nodes (the links are into `T`) to avoid extra allocations for the nodes (same as `Crystal::PointerLinkedList(T)`). It also requires a `T#heap_compare` method, so we can use the same type for a min or max heap, or to build a more complex comparison.

Note: I also tried a 4-heap, and while it performs very well and only needs a flat array, the arbitrary deletion (e.g. cancelling timeout) needs a linear scan and its performance quickly plummets, even at low occupancy, and becomes painfully slow at higher occupancy (tens of microseconds on _each_ delete, while the pairing heap does it in tens of nanoseconds).

Follow up to #14996 

[Mergeable Heap]: https://en.wikipedia.org/wiki/Mergeable_heap
[Pairing Heap]: https://en.wikipedia.org/wiki/Pairing_heap
[D-ary Heap]: https://en.wikipedia.org/wiki/D-ary_heap

Co-authored-by: Linus Sellberg <linus.sellberg@nj.se>
Co-authored-by: Johannes Müller <straightshoota@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant