Improve performance of Files.walk on the JVM by mpilquist · Pull Request #3383 · typelevel/fs2

mpilquist · 2024-02-04T14:43:22Z

For small walks, the overhead of the fs2/ce machinery dominates. For large walks, fs2's performance is within ~25% or so of the jvm's performance. For example, using @djspiewak's scenario with `MaxDepth = 7', I get:

fs2 took: 6600 ms
nio took: 5291 ms

djspiewak

I'm assuming the reason the overhead begins to converge in larger traversals is because there's a single big eval.

djspiewak · 2024-02-04T17:18:49Z

io/jvm-native/src/main/scala/fs2/io/file/FilesPlatform.scala

+                  bldr += Path.fromNioPath(path)
+                  size += 1
+                  if (size >= limit) {
+                    val result = dispatcher.unsafeRunSync(channel.send(Chunk.from(bldr.result())))


I really wish there were a way to suspend the visitation and continue it later. That would allow us to avoid the unsafeRunSync here and use unsafeRunAndForget instead, likely bouncing out of the interruptible once every n enqueues and passing through a Stream#append in order to preserve backpressure.

Is walkFileTree meaningfully faster than just doing the traversal by hand?

Even eagerly collecting everything is only 5% faster than the channel based solution (using the 4096 limit):

def walkEager(start: Path, maxDepth: Int, followLinks: Boolean): Stream[F, Path] = { val doWalk = Sync[F].interruptibleMany { val bldr = Vector.newBuilder[Path] JFiles.walkFileTree( start.toNioPath, if (followLinks) Set(FileVisitOption.FOLLOW_LINKS).asJava else Set.empty.asJava, maxDepth, new SimpleFileVisitor[JPath] { private def enqueue(path: JPath): FileVisitResult = { bldr += Path.fromNioPath(path) FileVisitResult.CONTINUE } override def visitFile(file: JPath, attrs: JBasicFileAttributes): FileVisitResult = enqueue(file) override def visitFileFailed(file: JPath, t: IOException): FileVisitResult = FileVisitResult.CONTINUE override def preVisitDirectory(dir: JPath, attrs: JBasicFileAttributes): FileVisitResult = enqueue(dir) override def postVisitDirectory(dir: JPath, t: IOException): FileVisitResult = FileVisitResult.CONTINUE } ) Chunk.from(bldr.result()) } Stream.eval(doWalk).flatMap(Stream.chunk) }

Wow, that's wild honestly. Have to ponder that. It's nice that we can just be lazy about our thread blocking though, since it simplifies this stuff.

@djspiewak BTW, there's a bunch of performance hackery in the JDK's file walking that's not (directly) available to us if we implement our own walk. For example, Path can cache file attributes avoiding some filesystem calls.

Just to close this out, I tried this prototype:

override def walk( start: Path, maxDepth: Int, followLinks: Boolean, chunkSize: Int ): Stream[F, Path] = walkJustInTime(start, maxDepth, followLinks, chunkSize) // if (chunkSize == Int.MaxValue) walkEager(start, maxDepth, followLinks) // else walkLazy(start, maxDepth, followLinks, chunkSize) private def walkJustInTime( start: Path, maxDepth: Int, followLinks: Boolean, chunkSize: Int ): Stream[F, Path] = { def loop(acc: Vector[Path], toWalk: Vector[Path]): Stream[F, Path] = { if (toWalk.isEmpty) { Stream.chunk(Chunk.from(acc)) } else { val path = toWalk.head val (toEmit, newAcc) = if (acc.size + 1 >= chunkSize) (Chunk.from(acc :+ path), Vector.empty) else (Chunk.empty, acc :+ path) val list = Sync[F].interruptibleMany { val npath = path.toNioPath if (JFiles.isDirectory(npath)) { val listing = JFiles.list(npath) try listing.iterator.asScala.map(Path.fromNioPath).toVector finally listing.close() } else Vector.empty } Stream.chunk(toEmit) ++ Stream.eval(list).flatMap(descendants => loop(newAcc, toWalk.drop(1) ++ descendants)) } } loop(Vector.empty, Vector(start)) }

Using MaxDepth = 7, I got these results:

fs2 took: 16070 ms fs2 eager took: 13935 ms nio took: 6356 ms

Whereas the implementation in this PR results in:

fs2 took: 8000 ms fs2 eager took: 5975 ms nio took: 6858 ms

Here's a better prototype that does file attribute reading at the time of directory listing.

asdf private def walkJustInTime( start: Path, maxDepth: Int, followLinks: Boolean, chunkSize: Int ): Stream[F, Path] = { def loop(acc: Vector[Path], toWalk: Vector[(Path, JBasicFileAttributes)]): Stream[F, Path] = { if (toWalk.isEmpty) { Stream.chunk(Chunk.from(acc)) } else { val (path, attr) = toWalk.head val (toEmit, newAcc) = if (acc.size + 1 >= chunkSize) (Chunk.from(acc :+ path), Vector.empty) else (Chunk.empty, acc :+ path) if (attr.isDirectory) { val list = Sync[F].interruptibleMany { val listing = JFiles.list(path.toNioPath) try listing.iterator.asScala.map(p => (Path.fromNioPath(p), JFiles.readAttributes(p, classOf[JBasicFileAttributes]))).toVector finally listing.close() } Stream.chunk(toEmit) ++ Stream.eval(list).flatMap(descendants => loop(newAcc, toWalk.drop(1) ++ descendants)) } else Stream.chunk(toEmit) ++ loop(newAcc, toWalk.drop(1)) } } Stream.eval(Sync[F].interruptibleMany { start -> JFiles.readAttributes(start.toNioPath, classOf[JBasicFileAttributes]) }).flatMap { s => loop(Vector.empty, Vector(s)) } }

Performs better but still doesn't beat the walkFileTree solution:

fs2 took: 10399 ms fs2 eager took: 8843 ms nio took: 7202 ms

Alright, maybe we should switch to a version based on this:

private def walkJustInTime( start: Path, maxDepth: Int, followLinks: Boolean, chunkSize: Int ): Stream[F, Path] = { import scala.collection.immutable.Queue def loop(toWalk0: Queue[(Path, JBasicFileAttributes)]): Stream[F, Path] = { val partialWalk = Sync[F].interruptibleMany { var acc = Vector.empty[Path] var toWalk = toWalk0 while (acc.size < chunkSize && toWalk.nonEmpty) { val (path, attr) = toWalk.head toWalk = toWalk.drop(1) acc = acc :+ path if (attr.isDirectory) { val listing = JFiles.list(path.toNioPath) try { val descendants = listing.iterator.asScala.map(p => (Path.fromNioPath(p), JFiles.readAttributes(p, classOf[JBasicFileAttributes]))).toVector toWalk = toWalk ++ descendants } finally listing.close() } } Stream.chunk(Chunk.from(acc)) ++ (if (toWalk.isEmpty) Stream.empty else loop(toWalk)) } Stream.eval(partialWalk).flatten } Stream.eval(Sync[F].interruptibleMany { start -> JFiles.readAttributes(start.toNioPath, classOf[JBasicFileAttributes]) }).flatMap(s => loop(Queue(s))) }

fs2 took: 9312 ms fs2 eager took: 8538 ms nio took: 7769 ms

So basically what we're trying to figure out is whether it's worth eating 9% overhead to avoid blocking a thread which is already getting blocked by filesystem I/O? My guess is that it's not worth it but I shall ponder a bit.

Pushed a new version:

fs2 took: 8131 ms fs2 eager took: 5950 ms nio took: 7346 ms

I'd like to add some tests for symbolic link following & max depth limits (we don't have any now). Then this PR should be good.

djspiewak · 2024-02-04T17:23:53Z

io/jvm-native/src/main/scala/fs2/io/file/FilesPlatform.scala


+    override def walk(start: Path, maxDepth: Int, followLinks: Boolean): Stream[F, Path] =
+      Stream.resource(Dispatcher.sequential[F]).flatMap { dispatcher =>
+        Stream.eval(Channel.bounded[F, Chunk[Path]](10)).flatMap { channel =>


Btw @armanbilge one thing that occurs to me is that our fancy new unsafe queue thing isn't going to help very much if someone's using Channel.

io/jvm/src/main/scala/fs2/io/file/AsyncFilesPlatform.scala

mpilquist · 2024-02-10T21:32:32Z

It appears Files.walkFileTree on Scala Native doesn't throw FileSystemLoopException. We could just skip the walkEager optimization on Scala Native for now I guess but then we're back to more platform specific traits.

Opened scala-native/scala-native#3744 for tracking upstream.

…wing cycles while following links

mpilquist · 2024-02-11T15:45:12Z

Okay this is ready for final review. Here's how we netted out performance wise:

fs2 took: 7574 ms
fs2 eager took: 5809 ms
nio took: 6956 ms

djspiewak · 2024-02-11T21:06:41Z

io/jvm-native/src/main/scala/fs2/io/file/FilesPlatform.scala

        .flatMap(ds => Stream.fromBlockingIterator[F](collectionIterator(ds), pathStreamChunkSize))

+    protected def walkEager(start: Path, options: WalkOptions): Stream[F, Path] = {
+      val doWalk = Sync[F].interruptibleMany {


Does it really need the Many?

djspiewak · 2024-02-11T21:07:24Z

io/jvm-native/src/main/scala/fs2/io/file/FilesPlatform.scala

+          var acc = Vector.empty[Path]
+          var toWalk = toWalk0
+
+          while (acc.size < options.chunkSize && toWalk.nonEmpty) {


May be worth checking Thread.interrupted()

mpilquist added 2 commits February 4, 2024 09:41

Improve performance of Files.walk on the JVM

1f07787

Scalafmt

e9bf35a

djspiewak reviewed Feb 4, 2024

View reviewed changes

mpilquist added 3 commits February 4, 2024 14:55

Fix native

81eee78

Scalafmt

18107f4

Reduce channel bound

9a915eb

djspiewak reviewed Feb 5, 2024

View reviewed changes

io/jvm/src/main/scala/fs2/io/file/AsyncFilesPlatform.scala Outdated Show resolved Hide resolved

mpilquist added 4 commits February 10, 2024 09:37

Switch to synchronous channel

a5bd763

Switch to just in time implementation

c7358a6

Add more tests

09b95f8

Make test cleanup more lenient

73be7b9

mpilquist added 2 commits February 10, 2024 17:45

Disable eager walks on Scala Native

64987f7

Update walk api to take an options parameter and add support for allo…

6b171f5

…wing cycles while following links

djspiewak reviewed Feb 11, 2024

View reviewed changes

Fix interruption

375942e

mpilquist merged commit 768039d into typelevel:main Feb 16, 2024

mpilquist deleted the topic/walk-performance branch February 16, 2024 15:22

Uh oh!

Conversation

mpilquist commented Feb 4, 2024

Uh oh!

djspiewak left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mpilquist Feb 10, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

mpilquist commented Feb 10, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mpilquist commented Feb 11, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

mpilquist Feb 10, 2024 •

edited

Loading

mpilquist commented Feb 10, 2024 •

edited

Loading