Skip to content

feat: add two new schedulers#3113

Closed
fgvieira wants to merge 16 commits intosnakemake:mainfrom
fgvieira:sched_greedier_naive
Closed

feat: add two new schedulers#3113
fgvieira wants to merge 16 commits intosnakemake:mainfrom
fgvieira:sched_greedier_naive

Conversation

@fgvieira
Copy link
Copy Markdown
Contributor

@fgvieira fgvieira commented Oct 4, 2024

Similarly to #3112, the scheduler can be quite slow. In this PR, me and @lczech have implemented two new schedulers, a greedier and a naive. For a simulated case of 500k ready jobs:

import timeit
import uuid
from random import uniform, seed
seed(10)
N=500000
jobs = [uuid.uuid4() for i in range(0,N)]
# prior, temp, input
r = [[int(uniform(1,10)),int(uniform(1,100000)),int(uniform(1,100000))] for i in range(0,N)]
res = [500000, 90, 9223372036854775798, 100]

The greedier is over 250x faster, while the naive is practically instantaneous:

In [16]: timeit.timeit(lambda: job_selector_naive(jobs, res), number=10)
Out[16]: 0.0018621431663632393

In [17]: timeit.timeit(lambda: job_selector_greedier(jobs, r, res), number=10)
Out[17]: 0.6542632929049432

In [18]: timeit.timeit(lambda: job_selector_greedy(jobs, r, res), number=10)
Out[18]: 176.2859104173258

As for the results, the greedier gives results similar to the current greedy implementation, while the naive is close but sub-optimal:

In [19]: job_selector_greedier(jobs, r, res) == job_selector_greedy(jobs, r, res)
Out[19]: True

In [20]: len(job_selector_greedier(jobs, r, res))
Out[20]: 17

In [21]: len(job_selector_naive(jobs, res))
Out[21]: 15

In [25]: set(job_selector_greedier(jobs, r, res)).intersection(set(job_selector_naive(jobs, res)))
Out[25]: set()
Simulation code
# mem_mb, cores, nodes, job_count
def job_weight(job):
    from random import uniform, seed
    seed(int("".join(c for c in str(job) if not c.isalpha() and c!="-")))
    return [int(uniform(1,10000)),int(uniform(1,10)),int(uniform(1,2)),int(uniform(1,2))]

def job_selector_greedy(jobs, rewards, res):
    n = len(jobs)
    x = [0] * n
    E = set(range(n))
    u = [1] * n
    a = list(map(job_weight, jobs))
    b = res
    c = rewards

    def calc_reward():
        return [c_j * y_j for c_j, y_j in zip(c, y)]

    while True:
        y = [
            (
                min(
                    (min(u[j], b_i // a_j_i) if a_j_i > 0 else u[j])
                    for b_i, a_j_i in zip(b, a[j])
                    if a_j_i
                )
                if j in E
                else 0
            )
            for j in range(n)
        ]
        if not any(y):
            break
        y = [
            (max(1, int(1 * y_j)) if y_j > 0 else 0) for y_j in y
        ]

        reward = calc_reward()
        j_sel = max(E, key=reward.__getitem__)

        y_sel = y[j_sel]

        x[j_sel] += y_sel
        b = [b_i - (a_j_i * y_sel) for b_i, a_j_i in zip(b, a[j_sel])]
        u[j_sel] -= y_sel
        if not u[j_sel] or self.greediness == 1:
            E.remove(j_sel)
        if not E:
            break

    solution = set(job for job, sel in zip(jobs, x) if sel)
    return solution

def job_selector_greedier(jobs, rewards, res, greediness = 1):
    import heapq

    n = (1 - greediness) * len(jobs) + greediness * min(res[1], res[2])
    heap = []
    for idx, job in enumerate(jobs):
        if n == 0 or len(heap) < n:
            heapq.heappush(heap, (rewards[idx], job))
        else:
            heapq.heappushpop(heap, (rewards[idx], job))

    max_sorted = [heapq.heappop(heap) for i in range(len(heap))]

    used_res = [0] * len(res)
    solution = set()
    while max_sorted:
        reward, job = max_sorted.pop()
        job_res = job_weight(job)
        assert len(job_res) == len(res)

        exhausted_some_res = False
        for i in range(len(res)):
            if used_res[i] + job_res[i] > res[i]:
                exhausted_some_res = True
                break

        if not exhausted_some_res:
            for i in range(len(res)):
                used_res[i] += job_res[i]
            solution.add(job)
    return solution


def job_selector_naive(jobs, res):
    used_res = [0] * len(res)
    solution = set()
    for job in jobs:
        job_res = job_weight(job)
        assert len(job_res) == len(res)

        exhausted_some_res = False
        for i in range(len(res)):
            used_res[i] += job_res[i]
            if used_res[i] > res[i]:
                exhausted_some_res = True
                break

        if exhausted_some_res:
            break
        else:
            solution.add(job)
    return solution

QC

  • The PR contains a test case for the changes or the changes are already covered by an existing test case.
  • The documentation (docs/) is updated to reflect the changes or this is not necessary (e.g. if the change does neither modify the language nor the behavior or functionalities of Snakemake).

Summary by CodeRabbit

  • New Features

    • Expanded job selection algorithms with new options: greedier and naive.
    • Introduced --wms-monitor argument for specifying workflow management system details.
    • Added --wms-monitor-arg for providing additional parameters to the workflow management service.
  • Enhancements

    • Improved command-line interface usability with clearer argument descriptions.
    • Modularized job selection process for better flexibility and efficiency.
  • Bug Fixes

    • Updated resource management logic to ensure accurate tracking based on selected jobs.

@coderabbitai
Copy link
Copy Markdown
Contributor

coderabbitai bot commented Oct 4, 2024

📝 Walkthrough

Walkthrough

The changes in this pull request involve updates to the command-line interface and job selection logic within the Snakemake framework. The snakemake/cli.py file has been modified to expand the --scheduler options and introduce new arguments for workflow monitoring. In snakemake/scheduler.py, the job selection strategies have been enhanced by adding new methods and modifying existing ones to accommodate multiple scheduling algorithms. These updates improve the functionality and usability of job scheduling and monitoring within Snakemake.

Changes

File Change Summary
snakemake/cli.py - Expanded --scheduler options from ["ilp", "greedy"] to ["ilp", "greedy", "greedier", "naive"].
- Added --wms-monitor argument for specifying workflow management system details.
- Added --wms-monitor-arg for extra key-value arguments.
- Refined help text for existing arguments for clarity.
snakemake/scheduler.py - Added methods: job_selector_naive, job_selector_greedier.
- Updated job_selector method signature.
- Updated job_reward method signature.
- Added jobs_rewards method for structured job reward computation.
- Enhanced job selection logic to support multiple strategies.

Possibly related PRs

Suggested reviewers

  • johanneskoester
✨ Finishing Touches
  • 📝 Generate Docstrings

🪧 Tips

Chat

There are 3 ways to chat with CodeRabbit:

  • Review comments: Directly reply to a review comment made by CodeRabbit. Example:
    • I pushed a fix in commit <commit_id>, please review it.
    • Generate unit testing code for this file.
    • Open a follow-up GitHub issue for this discussion.
  • Files and specific lines of code (under the "Files changed" tab): Tag @coderabbitai in a new review comment at the desired location with your query. Examples:
    • @coderabbitai generate unit testing code for this file.
    • @coderabbitai modularize this function.
  • PR comments: Tag @coderabbitai in a new PR comment to ask questions about the PR branch. For the best results, please provide a very specific query, as very limited context is provided in this mode. Examples:
    • @coderabbitai gather interesting stats about this repository and render them as a table. Additionally, render a pie chart showing the language distribution in the codebase.
    • @coderabbitai read src/utils.ts and generate unit testing code.
    • @coderabbitai read the files in the src/scheduler package and generate a class diagram using mermaid and a README in the markdown format.
    • @coderabbitai help me debug CodeRabbit configuration file.

Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments.

CodeRabbit Commands (Invoked using PR comments)

  • @coderabbitai pause to pause the reviews on a PR.
  • @coderabbitai resume to resume the paused reviews.
  • @coderabbitai review to trigger an incremental review. This is useful when automatic reviews are disabled for the repository.
  • @coderabbitai full review to do a full review from scratch and review all the files again.
  • @coderabbitai summary to regenerate the summary of the PR.
  • @coderabbitai generate docstrings to generate docstrings for this PR.
  • @coderabbitai resolve resolve all the CodeRabbit review comments.
  • @coderabbitai configuration to show the current CodeRabbit configuration for the repository.
  • @coderabbitai help to get help.

Other keywords and placeholders

  • Add @coderabbitai ignore anywhere in the PR description to prevent this PR from being reviewed.
  • Add @coderabbitai summary to generate the high-level summary at a specific location in the PR description.
  • Add @coderabbitai anywhere in the PR title to generate the title automatically.

CodeRabbit Configuration File (.coderabbit.yaml)

  • You can programmatically configure CodeRabbit by adding a .coderabbit.yaml file to the root of your repository.
  • Please see the configuration documentation for more information.
  • If your editor has YAML language server enabled, you can add the path at the top of this file to enable auto-completion and validation: # yaml-language-server: $schema=https://coderabbit.ai/integrations/schema.v2.json

Documentation and Community

  • Visit our Documentation for detailed information on how to use CodeRabbit.
  • Join our Discord Community to get help, request features, and share feedback.
  • Follow us on X/Twitter for updates and announcements.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 4

🧹 Outside diff range and nitpick comments (1)
snakemake/cli.py (1)

821-826: Clarify the help text for the --scheduler argument

The phrase "increasing sub-optimal solutions" in the help text may be misleading. Consider rephrasing it to "producing less optimal scheduling solutions" or "resulting in less optimal scheduling" to better convey that these algorithms may produce schedules that are not as optimal but are generated more quickly.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 19a2ab7 and 882b0c9.

📒 Files selected for processing (2)
  • snakemake/cli.py (1 hunks)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (2)
snakemake/cli.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

🪛 Ruff
snakemake/scheduler.py

801-801: Undefined name res

(F821)

@lczech
Copy link
Copy Markdown

lczech commented Oct 4, 2024

Thanks @fgvieira for preparing the PR!

To give some context: We are having a use case with many (millions) of rather small jobs, where each job execution is ~1sec, but the scheduler takes a full minute to select the next batch of jobs to be run, and is hence the main limiting factor for throughput.

The algorithms proposed here solve this in two distinct ways:

  • The greedier is a greedy solver for the knapsack problem, similar in principle to the existing greedy algorithm, but boiled down to the bare minimum: (1) Sort jobs by priority (reward), and (2) Select greedily from that list until a resource is exhausted.

    As we want a selection anyway, we can also speed up the sorting of jobs to begin with: We limit the number of jobs that are kept for sorting based on the greediness parameter (which is already present in snakemake), using a min heap. For greediness=0, we sort all jobs. For greediness=1, we only sort to find the n most rewarding jobs (by limiting the size of the heap), where n is the maximum number of jobs that we want to run in parallel anyway (based on max cores or nodes). In between, we use linear interpolation for the number of jobs kept on the heap: The less greedy, the more jobs are kept during sorting and can be taken into account for the selection.

    The more greedy, the faster, as the selection will only need to compute and compare resources for a limited number of jobs. But also, the more greedy, the more likely it is that we under-utilize resources, as there might be jobs later on in the list that could be "squeezed in", but are ignored due to not being on the heap after the sorting. But for the use case of many near-identical jobs, this scheduler should work fine.

  • The naive is even faster, and even more naive: It completely ignores priority/reward, does not sort anything, and just picks jobs from the list until resources are exhausted. We might call this "egalitarian", as it treats each job as equally important. This is even better for a long list of near-identical jobs, where reward does not differ/matter much, and we just quickly want to get going with submitting jobs.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 4

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 882b0c9 and f579e36.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 3

🧹 Outside diff range and nitpick comments (1)
snakemake/scheduler.py (1)

698-701: Remove unused function and approve changes.

The changes to the job_selector_greedy method are minor and don't alter the core logic. However, there's an unused function that can be removed.

Remove the unused calc_reward function:

- def calc_reward():
-     return [c_j * y_j for c_j, y_j in zip(c, y)]

This will clean up the code and remove unnecessary elements.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between f579e36 and 4e48d80.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

🔇 Additional comments (1)
snakemake/scheduler.py (1)

130-136: LGTM: Job selector assignment logic is correct and clear.

The implementation correctly assigns the appropriate job selector method based on the scheduler setting. This allows for flexible scheduling strategies.

@lczech
Copy link
Copy Markdown

lczech commented Oct 4, 2024

@johanneskoester and Snakemake team, one thing that is still a bit unclear to me is the computation of the rewards. As far as I could make sense of the existing implementation here, there are three values (job.priority, temp_size, input_size) being used, in a weighted sum with weights y. However, y is computed using u, which seems to be an indicator with the only possible values being 0 and 1. So does that mean that the reward is just a simple sum of priority, temp_size, and input_size? That's how we have it implemented in our code now, but it does seem weird, as those could be on very different orders of magnitude. Your input would be highly appreciated here!

@johanneskoester
Copy link
Copy Markdown
Contributor

Thanks a lot, very interesting! I will try to assess this as soon as possible. This comes timely as I anyway had the plan to finalize the plugin APIs of Snakemake soon, including scheduler plugins and deployment plugins. Maybe I manage to do that next week.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 1

🧹 Outside diff range and nitpick comments (2)
snakemake/scheduler.py (2)

811-846: LGTM: Simple and effective implementation of the naive job selector.

The job_selector_naive method is well-implemented, providing a straightforward approach to job selection. It correctly checks resource constraints before adding jobs to the solution.

Consider optimizing the resource checking loop.

The current implementation uses a separate loop for checking resources and another for updating them. This can be optimized for better performance.

Consider applying this optimization:

- # Check resources
- exhausted_some_res = False
- for i in range(len(max_glob_res)):
-     # Check if exceeds max
-     if used_res[i] + job_res[i] > max_glob_res[i]:
-         exhausted_some_res = True
-         break
-
- # Check if limits exceeded
- if exhausted_some_res:
-     break
- else:
-     # Update total resources
-     for i in range(len(max_glob_res)):
-         used_res[i] += job_res[i]
-     # Add job
-     solution.add(job)

+ # Check resources and update if possible
+ if all(used_res[i] + job_res[i] <= max_glob_res[i] for i in range(len(max_glob_res))):
+     # Update total resources
+     used_res = [used + job for used, job in zip(used_res, job_res)]
+     # Add job
+     solution.add(job)
+ else:
+     break

This change combines the resource checking and updating into a single loop, potentially improving performance for large numbers of jobs.


Line range hint 698-742: LGTM: Improved efficiency with asynchronous reward calculation.

The use of async_run(self.jobs_rewards(jobs)) is a good improvement, potentially enhancing the efficiency of reward calculation for multiple jobs.

Remove unused calc_reward function.

The calc_reward function is defined but never used in this method. It's best to remove unused code to maintain cleanliness and prevent confusion.

Apply this diff to remove the unused function:

- def calc_reward():
-     return [c_j * y_j for c_j, y_j in zip(c, y)]
📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 4e48d80 and 1dd31ba.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

📓 Learnings (1)
snakemake/scheduler.py (1)
Learnt from: lczech
PR: snakemake/snakemake#3113
File: snakemake/scheduler.py:912-914
Timestamp: 2024-10-04T16:12:18.927Z
Learning: In `snakemake/scheduler.py`, avoid suggesting the use of `asyncio.gather` in the `jobs_rewards` method due to overhead concerns and the need for immediate results.
🪛 Ruff
snakemake/scheduler.py

797-797: Undefined name res

(F821)


797-797: Undefined name res

(F821)

🔇 Additional comments (2)
snakemake/scheduler.py (2)

130-137: LGTM: Job selector assignment logic looks good.

The new job selector assignment logic is clear, concise, and covers all possible scheduler options. It's a good addition that allows for flexible scheduling strategies.


913-915: LGTM: Efficient asynchronous implementation of jobs_rewards.

The jobs_rewards method is well-implemented, providing an efficient way to calculate rewards for multiple jobs asynchronously. The use of a list comprehension with await is a good choice, allowing for concurrent reward calculations without the overhead of asyncio.gather, which aligns with the previous feedback about immediate result needs and potential overhead concerns.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 0

🧹 Outside diff range and nitpick comments (1)
snakemake/cli.py (1)

821-826: Correct grammatical errors and improve clarity in help text for --scheduler argument

The help text contains grammatical errors and typos:

  • The phrase "increasing sub-optimal solutions" should be rephrased to "obtaining sub-optimal solutions" for clarity.
  • "100s of thousand of similar jobs" should be corrected to "hundreds of thousands of similar jobs".

Apply this diff to improve the help text:

"The greedy, greedier and naive algorithms aim at reducing the scheduler runtime at the expense of"
-increasing sub-optimal solutions (but useful if dealing with 100s of thousand of similar jobs)."
+obtaining sub-optimal solutions (but useful when dealing with hundreds of thousands of similar jobs)."
📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 1dd31ba and a98bf6c.

📒 Files selected for processing (1)
  • snakemake/cli.py (1 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/cli.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 0

🧹 Outside diff range and nitpick comments (2)
snakemake/scheduler.py (2)

698-701: Remove unused calc_reward function.

The calc_reward function defined inside job_selector_greedy is not used within the method. Consider removing this unused function to improve code clarity.


910-912: LGTM: Efficient asynchronous implementation of jobs_rewards.

The jobs_rewards method efficiently calculates rewards for multiple jobs asynchronously. This implementation is suitable for most scenarios.

However, for very large numbers of jobs, consider using asyncio.gather to potentially improve performance:

async def jobs_rewards(self, jobs):
    return await asyncio.gather(*(self.job_reward(job) for job in jobs))

This change could allow for more efficient parallel execution of reward calculations.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between a98bf6c and 0226ab9.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

📓 Learnings (1)
snakemake/scheduler.py (1)
Learnt from: lczech
PR: snakemake/snakemake#3113
File: snakemake/scheduler.py:912-914
Timestamp: 2024-10-04T16:12:18.927Z
Learning: In `snakemake/scheduler.py`, avoid suggesting the use of `asyncio.gather` in the `jobs_rewards` method due to overhead concerns and the need for immediate results.
🔇 Additional comments (4)
snakemake/scheduler.py (4)

130-137: LGTM: Flexible job selector assignment implemented.

The implementation of different job selection strategies based on the scheduler setting is well-structured and provides good flexibility. The addition of "naive" and "greedier" schedulers expands the options for job selection, which can be beneficial for different workload scenarios.


743-809: LGTM: Efficient implementation of greedier job selector.

The job_selector_greedier method is well-implemented, using a heap for efficient job selection based on rewards. The greediness calculation allows for flexibility in job selection, and resource constraints are properly checked before adding jobs to the solution.


811-843: LGTM: Simple and correct implementation of naive job selector.

The job_selector_naive method provides a straightforward implementation for job selection. It iterates through jobs, adding them to the solution until resources are exhausted. This simple approach can be useful in scenarios where a more complex selection strategy is not necessary.


910-912: LGTM: Type annotations added to job_reward method.

The addition of type annotations to the job_reward method improves code readability and maintainability. This change aligns with best practices for Python development.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 0

🧹 Outside diff range and nitpick comments (3)
snakemake/scheduler.py (3)

698-701: Consider removing unused function calc_reward.

The calc_reward function is defined but not used in the provided code segment. It might be leftover code from a previous implementation. Consider removing it to improve code clarity.


743-811: LGTM: Efficient implementation of the greedier job selector.

The job_selector_greedier method is well-implemented, using a heap for efficient job selection based on rewards. The greediness calculation allows for flexibility in job selection, and resource constraints are properly checked before adding jobs to the solution.

Consider adding comments to explain the key steps of the algorithm, such as the greediness calculation and the heap usage, to improve code readability and maintainability.


812-845: LGTM: Simple and correct implementation of the naive job selector.

The job_selector_naive method is implemented correctly, iterating through jobs and adding them to the solution until resources are exhausted. This approach is appropriately simple for a naive selector, not considering job rewards or priorities.

Consider adding a brief comment explaining that this method doesn't take job priorities into account, which might be useful for users or maintainers of the code.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 0226ab9 and 9f4c0d6.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

📓 Learnings (1)
snakemake/scheduler.py (1)
Learnt from: lczech
PR: snakemake/snakemake#3113
File: snakemake/scheduler.py:912-914
Timestamp: 2024-10-04T16:12:18.927Z
Learning: In `snakemake/scheduler.py`, avoid suggesting the use of `asyncio.gather` in the `jobs_rewards` method due to overhead concerns and the need for immediate results.
🔇 Additional comments (3)
snakemake/scheduler.py (3)

130-137: LGTM: Job selector assignment looks good.

The implementation correctly assigns different job selector methods based on the scheduler setting. The structure is clear and ensures that only one selector is chosen.


740-742: LGTM: Proper update of available resources.

The update_available_resources method is correctly called with the solution set at the end of the job_selector_greedy method. This ensures that the available resources are accurately tracked after job selection.


912-914: LGTM: Efficient asynchronous implementation of jobs_rewards.

The jobs_rewards method is implemented correctly as an asynchronous method. It efficiently uses a list comprehension to calculate rewards for all jobs. This implementation is concise and makes good use of Python's asynchronous features.

@ASLeonard
Copy link
Copy Markdown
Contributor

I'm sure everyone has a different use-case/preference, but in the context of our HPC, I would much rather just have all the jobs submitted quickly rather than submitted in an optimal order but slowly. The naive or greedier schedulers sound ideal. If there is a scheduler-plugin concept, the pulp dependency could also become optional, which seems to drop the number of packages installed from the snakemake recipe from 94 to 77.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 1

🧹 Outside diff range and nitpick comments (2)
snakemake/scheduler.py (2)

698-701: Remove unused function calc_reward.

The calc_reward function is defined but not used in the provided code segment. It appears to be a leftover from previous code. Consider removing it to improve code clarity and maintainability.

Apply this diff to remove the unused function:

-            def calc_reward():
-                return [c_j * y_j for c_j, y_j in zip(c, y)]

743-774: LGTM: Efficient implementation of greedy job selection.

The _job_selector_greedier method is well-implemented, using an efficient approach to select jobs until resources are exhausted. The use of any() for resource checking is a good Pythonic approach.

A minor suggestion for improved readability:

Consider renaming global_res to max_global_res or global_res_limits to more clearly indicate that these are the maximum resource capacities.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 9f4c0d6 and a64dd20.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

📓 Learnings (1)
snakemake/scheduler.py (1)
Learnt from: lczech
PR: snakemake/snakemake#3113
File: snakemake/scheduler.py:912-914
Timestamp: 2024-10-04T16:12:18.927Z
Learning: In `snakemake/scheduler.py`, avoid suggesting the use of `asyncio.gather` in the `jobs_rewards` method due to overhead concerns and the need for immediate results.
🔇 Additional comments (5)
snakemake/scheduler.py (5)

130-137: LGTM: Clear and correct job selector assignment.

The implementation of job selector assignment based on the scheduler setting is well-structured and correct. It provides a clear way to choose between different job selection strategies.


740-742: LGTM: Correct update of available resources.

The call to update_available_resources is correctly placed after job selection in the job_selector_greedy method. This ensures that resource availability is accurately maintained for subsequent scheduling rounds.


819-841: LGTM: Simple and efficient naive job selection.

The job_selector_naive method is well-implemented, providing a straightforward approach to job selection. The use of islice for selecting a subset of jobs is efficient, and the reuse of _job_selector_greedier for final selection promotes code reuse.


908-910: LGTM: Efficient asynchronous calculation of job rewards.

The jobs_rewards method is well-implemented, using asynchronous programming effectively to calculate rewards for multiple jobs. The use of a list comprehension with await makes the code concise and readable.


Line range hint 130-910: Overall assessment: Well-implemented job scheduling enhancements.

The changes to the JobScheduler class introduce new job selection strategies (naive and greedier) while improving the existing ones. The implementations are generally correct, efficient, and make good use of Python's features and asynchronous programming. The code is well-structured and promotes reusability.

Minor suggestions for improvement include:

  1. Removing an unused function in the greedy selector.
  2. Considering a minor optimization in the greedier selector using heapq.nlargest().
  3. Improving variable naming for clarity in some parts.

These changes significantly enhance the flexibility and efficiency of job scheduling in Snakemake.

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 0

🧹 Outside diff range and nitpick comments (1)
snakemake/scheduler.py (1)

775-817: LGTM: Efficient implementation of the greedier job selector.

The job_selector_greedier method is well-implemented, using a heap to efficiently select the most rewarding jobs. The calculation of n provides a good balance between considering all jobs and limiting to available resources.

A potential optimization:

Consider using heapq.nlargest() instead of manually popping elements from the heap. This could simplify the code and potentially be more efficient:

-            max_sorted = [heapq.heappop(heap)[1] for i in range(n)]
+            max_sorted = [job for _, job in heapq.nlargest(len(heap), heap)]

This change eliminates the need for manual heap operations while achieving the same result.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between a64dd20 and 2da80c8.

📒 Files selected for processing (1)
  • snakemake/scheduler.py (4 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/scheduler.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

📓 Learnings (1)
snakemake/scheduler.py (1)
Learnt from: lczech
PR: snakemake/snakemake#3113
File: snakemake/scheduler.py:912-914
Timestamp: 2024-10-04T16:12:18.927Z
Learning: In `snakemake/scheduler.py`, avoid suggesting the use of `asyncio.gather` in the `jobs_rewards` method due to overhead concerns and the need for immediate results.
🔇 Additional comments (6)
snakemake/scheduler.py (6)

130-137: LGTM: Job selector assignment logic is correct and clear.

The implementation correctly assigns the appropriate job selector based on the scheduler setting. This allows for easy extension of scheduling algorithms in the future.


743-773: LGTM: Correct implementation of the greedy job selection algorithm.

The _job_selector_greedier method efficiently selects jobs while respecting resource constraints. The implementation is clear and straightforward.


819-841: LGTM: Simple and effective implementation of the naive job selector.

The job_selector_naive method provides a straightforward approach to job selection. The use of islice to limit the number of jobs considered is an efficient way to implement the greediness parameter.


Line range hint 843-850: LGTM: Correct implementation of resource update.

The update_available_resources method accurately updates the available resources after job selection. The special handling of _job_count is appropriate.


Line range hint 878-907: LGTM: Improved job reward calculation.

The job_reward method now properly handles different workflow modes (touch, dryrun, immediate submit) and calculates rewards based on relevant factors (priority, temp file size, input size). This should lead to more effective job scheduling.


908-910: LGTM: Simple implementation of jobs_rewards method.

The jobs_rewards method correctly calculates rewards for multiple jobs. The implementation is clear and straightforward.

@sonarqubecloud
Copy link
Copy Markdown

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 0

🧹 Outside diff range and nitpick comments (2)
snakemake/cli.py (2)

817-822: Expanded scheduler options and improved help text.

The changes to the --scheduler argument are well-implemented and provide more flexibility to users. Here are the key improvements:

  1. Two new scheduler options have been added: "greedier" and "naive".
  2. The default scheduler is now set based on the availability of the recommended LP solver (COIN_CMD).
  3. The help text has been updated to explain the differences between the scheduler options.

These changes enhance the functionality and user-friendliness of the Snakemake CLI.

Consider adding brief descriptions of the new "greedier" and "naive" schedulers in the help text to give users a better understanding of when to use each option. For example:

help=(
    "Specifies if jobs are selected by solving an ILP, a greedy, a greedier, or a naive algorithm. "
    "The ILP scheduler aims to reduce runtime and HDD usage by best possible use of resources. "
    "The greedy scheduler balances optimization and speed. "
    "The greedier scheduler prioritizes speed over optimal resource usage. "
    "The naive scheduler is the fastest but may lead to suboptimal resource utilization. "
    "Choose based on your workflow complexity and performance requirements."
),

Line range hint 823-844: New WMS monitoring arguments added.

Two new arguments have been added to support workflow management system (WMS) monitoring:

  1. --wms-monitor: Allows specifying an IP and port for a WMS to monitor Snakemake execution.
  2. --wms-monitor-arg: Enables passing additional key-value pair arguments to the WMS endpoint.

These additions enhance Snakemake's integration capabilities with external monitoring systems. The implementation is clean and well-documented.

Consider adding a brief example in the help text for --wms-monitor-arg to illustrate its usage. For instance:

help=(
    "If the workflow management service accepts extra arguments, provide "
    "them in key value pairs with --wms-monitor-arg. For example: "
    "--wms-monitor-arg id=12345 status=running"
),

This would make it clearer to users how to format multiple arguments.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL

📥 Commits

Files that changed from the base of the PR and between 2da80c8 and fcd3d61.

📒 Files selected for processing (1)
  • snakemake/cli.py (1 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
snakemake/cli.py (1)

Pattern **/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

🔇 Additional comments (1)
snakemake/cli.py (1)

Line range hint 1-844: Overall assessment: Well-implemented enhancements to Snakemake CLI.

The changes made to snakemake/cli.py significantly improve the functionality and flexibility of the Snakemake command-line interface:

  1. Expanded scheduler options with the addition of "greedier" and "naive" algorithms.
  2. Improved scheduler selection logic based on available LP solvers.
  3. Added WMS monitoring capabilities with --wms-monitor and --wms-monitor-arg.

These enhancements provide users with more control over job scheduling and better integration with external monitoring systems. The implementation is clean, well-documented, and maintains consistency with the existing codebase.

While no major issues were found, consider implementing the suggested minor improvements to the help text for even better user experience.

@sonarqubecloud
Copy link
Copy Markdown

@fgvieira fgvieira moved this from Ready to In review in Snakemake Hackathon March 2025 Mar 10, 2025
@sonarqubecloud
Copy link
Copy Markdown

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 0

🧹 Nitpick comments (1)
snakemake/cli.py (1)

879-883: Clear explanation of scheduler options

The help text has been updated to explain the differences between the scheduler options, highlighting that the ILP scheduler optimizes resource usage while the greedy, greedier, and naive algorithms prioritize reducing scheduler runtime, potentially at the cost of solution optimality.

Consider enhancing the help text to include specific performance characteristics mentioned in the PR - such as the 'greedier' scheduler being 250x faster than 'greedy', and that 'naive' operates almost instantaneously. This would help users make an informed choice based on their specific use case.

📜 Review details

Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between 66744ec and 50abff0.

📒 Files selected for processing (1)
  • snakemake/cli.py (1 hunks)
🧰 Additional context used
📓 Path-based instructions (1)
`**/*.py`: Do not try to improve formatting. Do not suggest ...

**/*.py: Do not try to improve formatting.
Do not suggest type annotations for functions that are defined inside of functions or methods.
Do not suggest type annotation of the self argument of methods.
Do not suggest type annotation of the cls argument of classmethods.
Do not suggest return type annotation if a function or method does not contain a return statement.

  • snakemake/cli.py
⏰ Context from checks skipped due to timeout of 90000ms (40)
  • GitHub Check: testing (10, 3.12, dash)
  • GitHub Check: testing (10, 3.12, bash)
  • GitHub Check: testing (10, 3.11, bash)
  • GitHub Check: testing (9, 3.12, dash)
  • GitHub Check: testing (9, 3.12, bash)
  • GitHub Check: testing (9, 3.11, bash)
  • GitHub Check: testing (8, 3.12, dash)
  • GitHub Check: testing (8, 3.12, bash)
  • GitHub Check: testing (8, 3.11, bash)
  • GitHub Check: testing (7, 3.12, dash)
  • GitHub Check: testing (7, 3.12, bash)
  • GitHub Check: testing (7, 3.11, bash)
  • GitHub Check: testing (6, 3.12, dash)
  • GitHub Check: testing (6, 3.12, bash)
  • GitHub Check: testing (6, 3.11, bash)
  • GitHub Check: testing (5, 3.12, dash)
  • GitHub Check: testing (5, 3.12, bash)
  • GitHub Check: testing (5, 3.11, bash)
  • GitHub Check: testing (4, 3.12, dash)
  • GitHub Check: testing (4, 3.12, bash)
  • GitHub Check: testing (4, 3.11, bash)
  • GitHub Check: testing (3, 3.12, dash)
  • GitHub Check: testing (3, 3.12, bash)
  • GitHub Check: testing-windows (10)
  • GitHub Check: testing (3, 3.11, bash)
  • GitHub Check: testing-windows (9)
  • GitHub Check: testing (2, 3.12, dash)
  • GitHub Check: testing-windows (8)
  • GitHub Check: testing (2, 3.12, bash)
  • GitHub Check: testing-windows (7)
  • GitHub Check: testing (2, 3.11, bash)
  • GitHub Check: testing-windows (6)
  • GitHub Check: testing (1, 3.12, dash)
  • GitHub Check: testing-windows (5)
  • GitHub Check: testing (1, 3.12, bash)
  • GitHub Check: testing-windows (4)
  • GitHub Check: testing (1, 3.11, bash)
  • GitHub Check: testing-windows (3)
  • GitHub Check: testing-windows (2)
  • GitHub Check: testing-windows (1)
🔇 Additional comments (3)
snakemake/cli.py (3)

877-877: Updates to scheduler choices to include new options

The scheduler choices have been expanded to include the new 'greedier' and 'naive' options alongside the existing 'ilp' and 'greedy' options. This aligns with the PR objective to introduce more efficient schedulers for large job batches.


886-893: New monitoring functionality with --wms-monitor

Added a new command-line argument to enable workflow monitoring by allowing specification of an IP and port for a workflow management system. The help text properly explains the requirement for an authorization token.


894-905: Support for additional WMS arguments

Added a new command-line argument to provide extra key-value pairs to the workflow management service. The help text gives a clear example of how to use this option.

@johanneskoester
Copy link
Copy Markdown
Contributor

@fgvieira the scheduler plugin interface is released and can be used with snakemake 9.10: https://github.com/snakemake/snakemake-interface-scheduler-plugins
I would absolutely love to see these two schedulers as scheduler plugins!

@fgvieira
Copy link
Copy Markdown
Contributor Author

I've been a bit busy, but will try to turn these schedulers as plugins.

@fgvieira
Copy link
Copy Markdown
Contributor Author

@johanneskoester managed to make a first version of the scheduler plugin at fgvieira/snakemake-scheduler-plugin-firstfit. Let me know if you have any suggestions.

@fgvieira
Copy link
Copy Markdown
Contributor Author

Closing as this has been re-implemented as a plugin snakemake-scheduler-plugin-firstfit

@fgvieira fgvieira closed this Oct 16, 2025
@fgvieira fgvieira deleted the sched_greedier_naive branch October 17, 2025 17:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

Development

Successfully merging this pull request may close these issues.

4 participants