search

cmuparlay / parlaylib

A Toolkit for Programming Parallel Algorithms on Shared-Memory Multicore Machines
MIT License
320 stars 60 forks source link

Delayed sequence can be used for all algorithms that take random-access range? #79

Closed WhateverLiu closed 3 weeks ago

WhateverLiu commented 3 weeks ago

Dear Parlaylib maintainers,

I have been using the library with continuing excitement. For a time I thought delayed_sequence can only be supplied to primitives documented in Section "Delayed sequence algorithms" https://cmuparlay.github.io/parlaylib/algorithms/delayed.html.

But lately, I supplied reduce_by_key() (not in Section "Delayed sequence algorithm") with a delayed_sequence due to the massive data size, and it produced the correct result.

This makes me wonder, do all algorithms accepting random-access range will work correctly with delayed_sequence? By its definition it seems yes, but I just want to confirm it.

Thank you!

gblelloch commented 3 weeks ago

There is a distinction between a RAD and a BID delayed sequence, which is described in the paper: https://dl.acm.org/doi/10.1145/3503221.3508434

Any RAD delayed sequence can be used efficienctly by any algorithm that uses a random access range. It looks like all delayed sequences support op[] so I imagine it works for all delayed sequences but would not necessarily be fast for BID delayed sequences (Daniel, is this correct?)

Basically delayed map, delayed tabulate generate RADs but delayed scan generates a BID.

Guy

On Wed, Oct 30, 2024 at 1:28 AM CharlieWL @.***> wrote:

Dear Parlaylib maintainers,

I have been using the library with continuing excitement. For a time I thought delayed_sequence can only be supplied to primitives documented in Section "Delayed sequence algorithms" https://cmuparlay.github.io/parlaylib/algorithms/delayed.html.

But lately, I supplied reduce_by_key() (not in Section "Delayed sequence algorithm") with a delayed_sequence due to the massive data size, and it produced the correct result.

This makes me wonder, do all algorithms accepting random-access range will work correctly with delayed_sequence? By its definition it seems yes, but I just want to confirm it.

Thank you!

— Reply to this email directly, view it on GitHub https://github.com/cmuparlay/parlaylib/issues/79, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABTIVABR2V2RSMGGWQC3NHLZ6BU7TAVCNFSM6AAAAABQ3KMXPGVHI2DSMVQWIX3LMV43ASLTON2WKOZSGYZDEOJVGM4DINQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>

DanielLiamAnderson commented 3 weeks ago

delayed_sequence is a random-access range, so yes it should work on anything expecting a random-access range.