{"action":"created","issue":{"url":"https://api.github.com/repos/mpv-player/mpv/issues/6162","repository_url":"https://api.github.com/repos/mpv-player/mpv","labels_url":"https://api.github.com/repos/mpv-player/mpv/issues/6162/labels{/name}","comments_url":"https://api.github.com/repos/mpv-player/mpv/issues/6162/comments","events_url":"https://api.github.com/repos/mpv-player/mpv/issues/6162/events","html_url":"https://github.com/mpv-player/mpv/issues/6162","id":365056130,"node_id":"MDU6SXNzdWUzNjUwNTYxMzA=","number":6162,"title":"CPU cycles are massively wasted on playlist-pos change in large playlists","user":{"login":"VideoPlayerCode","id":38923130,"node_id":"MDQ6VXNlcjM4OTIzMTMw","avatar_url":"https://avatars0.githubusercontent.com/u/38923130?v=4","gravatar_id":"","url":"https://api.github.com/users/VideoPlayerCode","html_url":"https://github.com/VideoPlayerCode","followers_url":"https://api.github.com/users/VideoPlayerCode/followers","following_url":"https://api.github.com/users/VideoPlayerCode/following{/other_user}","gists_url":"https://api.github.com/users/VideoPlayerCode/gists{/gist_id}","starred_url":"https://api.github.com/users/VideoPlayerCode/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/VideoPlayerCode/subscriptions","organizations_url":"https://api.github.com/users/VideoPlayerCode/orgs","repos_url":"https://api.github.com/users/VideoPlayerCode/repos","events_url":"https://api.github.com/users/VideoPlayerCode/events{/privacy}","received_events_url":"https://api.github.com/users/VideoPlayerCode/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-09-28T22:06:55Z","updated_at":"2018-09-29T01:33:18Z","closed_at":null,"author_association":"NONE","body":"### mpv version and platform\r\n\r\nMac.\r\n\r\n_mpv 9efb027 Copyright © 2000-2018 mpv/MPlayer/mplayer2 projects\r\n built on Sat Apr 14 00:14:40 CEST 2018\r\nffmpeg library versions:\r\n   libavutil       56.13.100\r\n   libavcodec      58.17.100\r\n   libavformat     58.11.101\r\n   libswscale      5.0.102\r\n   libavfilter     7.15.100\r\n   libswresample   3.0.101\r\nffmpeg version: git-2018-04-13-37d46dc_\r\n\r\n### Reproduction steps\r\n\r\n1. Create this tiny Lua script _(I hastily threw together this code for the purpose of this ticket, but if someone reading this happens to actually want a proper, full-fledged randomizer for something, use [Leapfrog](https://github.com/VideoPlayerCode/mpv-tools/blob/master/scripts/Leapfrog.js) instead)_:\r\n\r\n```lua\r\nfunction random_jump()\r\n    local max = mp.get_property_number(\"playlist-count\");\r\n    local target = math.random(0, max - 1);\r\n    mp.osd_message(\"Target: \" .. target+1 .. \"/\" .. max)\r\n    mp.set_property(\"playlist-pos\", target);\r\nend\r\n\r\nmp.register_script_message(\"RandyJumper\", random_jump)\r\n```\r\n\r\n2. Bind the command in input.conf:\r\n\r\n```\r\nc script-message RandyJumper\r\n```\r\n\r\n3. Create a folder with 1,000 test images and open it in mpv:\r\n\r\n```\r\nmkdir test && cd test\r\nwget https://upload.wikimedia.org/wikipedia/commons/d/db/Patern_test.jpg -O 1.jpg\r\nfor i in {2..1000}; do cp 1.jpg \"$i.jpg\"; done\r\nmpv .\r\n```\r\n\r\n4. Press `c` to randomly jump to different images. This should be pretty much instant every time you press `c`. The new image will load, and your console (view the terminal you launched mpv from) will instantly show the new \"Playing:\" result for whatever file it jumped to.\r\n\r\n5. Create a bigger folder with 40,000 test images and open it in mpv:\r\n\r\n```\r\nmkdir bigtest && cd bigtest\r\nwget https://upload.wikimedia.org/wikipedia/commons/d/db/Patern_test.jpg -O 1.jpg\r\nfor i in {2..40000}; do cp 1.jpg \"$i.jpg\"; done\r\nmpv .\r\n```\r\n\r\n6. Press `c` to randomly jump in this larger playlist. If your result is like mine, it will take about a second between each jump. The terminal you launched mpv from will show veeeery slow navigation between files. And the OSD will be equally sluggish at showing the new \"Target: ...\" script message.\r\n\r\nThe time it takes grows the larger the playlist is. So 80,000 images is about two seconds, etc. _(And as a sidenote: If your computer is ultra-fast and doesn't have a problem at 40,000, then simply run the test again with more images, such as 100k instead!)_\r\n\r\nThese results are also replicable by a mere `v set playlist-pos 20000` command, so it has nothing to do with the scripting engine. Therefore it seems like there's a problem with setting the `playlist-pos` property, which causes massive slowdowns when there's a lot of files in the playlist.\r\n\r\nLikewise, prev/next buttons in mpv's regular on-screen controls, and even \"autoplay\" (via pressing spacebar to \"play\" the images) are also affected by the playlist-size dependent slowdown.\r\n\r\n### Expected behavior\r\n\r\nWhy should it matter if a playlist contains 1 file, 1000 files or 40,000 files? To mpv, there technically _shouldn't_ need to be any difference. It should be able to just look up the \"Xth\" entry of the playlist and proceed instantly regardless of whether the list has 10 or 100,000 entries.\r\n\r\nA playlist is basically just a small array of filenames, and 40,000 entries is \"nothing\" for a computer.\r\n\r\nBut somehow, the larger playlists cause massive slowdowns (\"1 second\" is massive by CPU-standards).\r\n\r\nSo mpv is clearly wasting _tons_ of CPU cycles doing \"something\" when playlists are large. The question is: What is mpv wasting its cycles on, and is it possible to fix that behavior?"},"comment":{"url":"https://api.github.com/repos/mpv-player/mpv/issues/comments/425605029","html_url":"https://github.com/mpv-player/mpv/issues/6162#issuecomment-425605029","issue_url":"https://api.github.com/repos/mpv-player/mpv/issues/6162","id":425605029,"node_id":"MDEyOklzc3VlQ29tbWVudDQyNTYwNTAyOQ==","user":{"login":"haasn","id":1149047,"node_id":"MDQ6VXNlcjExNDkwNDc=","avatar_url":"https://avatars0.githubusercontent.com/u/1149047?v=4","gravatar_id":"","url":"https://api.github.com/users/haasn","html_url":"https://github.com/haasn","followers_url":"https://api.github.com/users/haasn/followers","following_url":"https://api.github.com/users/haasn/following{/other_user}","gists_url":"https://api.github.com/users/haasn/gists{/gist_id}","starred_url":"https://api.github.com/users/haasn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haasn/subscriptions","organizations_url":"https://api.github.com/users/haasn/orgs","repos_url":"https://api.github.com/users/haasn/repos","events_url":"https://api.github.com/users/haasn/events{/privacy}","received_events_url":"https://api.github.com/users/haasn/received_events","type":"User","site_admin":false},"created_at":"2018-09-29T01:33:18Z","updated_at":"2018-09-29T01:33:18Z","author_association":"MEMBER","body":"> Why should it matter if a playlist contains 1 file, 1000 files or 40,000 files? To mpv, there technically shouldn't need to be any difference. It should be able to just look up the \"Xth\" entry of the playlist and proceed instantly regardless of whether the list has 10 or 100,000 entries.\r\n\r\nActually, playlists are stored as linked lists in mpv. Linked lists have other advantages, such as being able to add/remove entries or concatenate playlists in O(1), but come at the cost of slow seeking (O(n)). An array like you are suggesting would have the opposite issue - appending, inserting, or removing playlist entries would become much slower for large lists as well.\r\n\r\nBut we could get a best-of-both worlds tradeoff here by using some smarter structure like a finger tree, which would allow us O(log n) access with amortized O(1) insert/delete/append/concatenate.\r\n\r\nPatches welcome"}}
{"actor":{"display_login":"haasn"}}