• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

wooga / github-changelog-lib / 4
91%

Build:
DEFAULT BRANCH: master
Ran 05 Mar 2020 08:17AM UTC
Jobs 3
Files 11
Run time 815452min
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

pending completion
4

push

jenkins

Improve fiter commit algorithm (#4)

## Description

Implements #3 

The commit filter algorithm in the `DefaultChangeDetector` had an exponential complexity (it was searching multiple times the same paths from nodes to same nodes). This was sufficient for most normal wdk repos or other repos that heavily used only PR's.  But unfortunately it was taking too long on a busy repo like for example a game repo like @wooga/switchcraft .

This  PR changes the algorithm a bit in order to memoize the already computed paths.  It also adds a performance test on a worst-case scenario with 30 merges. (2^30 -> 1 billion OPS)

This reduced the complexity from O( E(branching factor)^V(nodes) ) to O( V^2+E) ). Also to be able to re-use multiple paths to the same head with various iterating base's, I reversed the traversal order. (from base->head), reducing the complexity even more to O(V+E)

## Changes
* ![IMPROVE] Adds memoization to commit filter algorithm to reduce complexity to O(V+E)

210 of 226 relevant lines covered (92.92%)

1.86 hits per line

Jobs
ID Job ID Ran Files Coverage
1 4.1 05 Mar 2020 08:17AM UTC 0
92.92
2 4.2 05 Mar 2020 08:17AM UTC 0
92.92
3 4.3 22 Sep 2021 03:07PM UTC 0
91.42
Source Files on build 4
Detailed source file information is not available for this build.
  • Back to Repo
  • Jenkins Build #4
  • 47c3b4a4 on github
  • Prev Build on master (#27)
  • Next Build on master (#28)
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc