{"action":"closed","number":419,"pull_request":{"url":"https://api.github.com/repos/samtools/samtools/pulls/419","id":38997729,"html_url":"https://github.com/samtools/samtools/pull/419","diff_url":"https://github.com/samtools/samtools/pull/419.diff","patch_url":"https://github.com/samtools/samtools/pull/419.patch","issue_url":"https://api.github.com/repos/samtools/samtools/issues/419","number":419,"state":"closed","locked":false,"title":"Header merge efficiency","user":{"login":"smowton","id":283483,"avatar_url":"https://avatars.githubusercontent.com/u/283483?v=3","gravatar_id":"","url":"https://api.github.com/users/smowton","html_url":"https://github.com/smowton","followers_url":"https://api.github.com/users/smowton/followers","following_url":"https://api.github.com/users/smowton/following{/other_user}","gists_url":"https://api.github.com/users/smowton/gists{/gist_id}","starred_url":"https://api.github.com/users/smowton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/smowton/subscriptions","organizations_url":"https://api.github.com/users/smowton/orgs","repos_url":"https://api.github.com/users/smowton/repos","events_url":"https://api.github.com/users/smowton/events{/privacy}","received_events_url":"https://api.github.com/users/smowton/received_events","type":"User","site_admin":false},"body":"Hi all,\r\n\r\nI was working with some BAM files that had a large number of contigs (they were aligned against parts of the NCBI NT database, which has thousands of short contigs). The input files had disjoint contigs, having been aligned to disjoint subsets of the database. This turned out to make 'samtools merge' prohibitively expensive, spending hours in `trans_tbl_init`.\r\n\r\nThis patch improves the situation by (a) switching from a quadratic search for `@SQ` lines in `translate->text` to a linear pass over it, (b) switching from using `regexec` et al to plain old `string.h` operations, making a pass over a single file much faster, and (c) allowing the hashtable used to build the global translation table to live between reading each input, avoid quadratic cost of repeatedly building and expanding the table when there are more than a few input files involved.\r\n\r\nThis is only lightly tested with the particular workload that was causing trouble, but if you think the use case (many small contigs) is interesting, this might be useful to incorporate.","created_at":"2015-07-01T16:02:10Z","updated_at":"2015-08-20T13:51:10Z","closed_at":"2015-08-20T13:51:10Z","merged_at":"2015-08-20T13:51:10Z","merge_commit_sha":"286f5944c36eff7241c4b4751770f181ee233ee7","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/samtools/samtools/pulls/419/commits","review_comments_url":"https://api.github.com/repos/samtools/samtools/pulls/419/comments","review_comment_url":"https://api.github.com/repos/samtools/samtools/pulls/comments{/number}","comments_url":"https://api.github.com/repos/samtools/samtools/issues/419/comments","statuses_url":"https://api.github.com/repos/samtools/samtools/statuses/a1814030f5a843e62619c61b3ffe857688e5d41e","head":{"label":"smowton:header_merge_efficiency","ref":"header_merge_efficiency","sha":"a1814030f5a843e62619c61b3ffe857688e5d41e","user":{"login":"smowton","id":283483,"avatar_url":"https://avatars.githubusercontent.com/u/283483?v=3","gravatar_id":"","url":"https://api.github.com/users/smowton","html_url":"https://github.com/smowton","followers_url":"https://api.github.com/users/smowton/followers","following_url":"https://api.github.com/users/smowton/following{/other_user}","gists_url":"https://api.github.com/users/smowton/gists{/gist_id}","starred_url":"https://api.github.com/users/smowton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/smowton/subscriptions","organizations_url":"https://api.github.com/users/smowton/orgs","repos_url":"https://api.github.com/users/smowton/repos","events_url":"https://api.github.com/users/smowton/events{/privacy}","received_events_url":"https://api.github.com/users/smowton/received_events","type":"User","site_admin":false},"repo":{"id":27885387,"name":"samtools","full_name":"smowton/samtools","owner":{"login":"smowton","id":283483,"avatar_url":"https://avatars.githubusercontent.com/u/283483?v=3","gravatar_id":"","url":"https://api.github.com/users/smowton","html_url":"https://github.com/smowton","followers_url":"https://api.github.com/users/smowton/followers","following_url":"https://api.github.com/users/smowton/following{/other_user}","gists_url":"https://api.github.com/users/smowton/gists{/gist_id}","starred_url":"https://api.github.com/users/smowton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/smowton/subscriptions","organizations_url":"https://api.github.com/users/smowton/orgs","repos_url":"https://api.github.com/users/smowton/repos","events_url":"https://api.github.com/users/smowton/events{/privacy}","received_events_url":"https://api.github.com/users/smowton/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/smowton/samtools","description":"Tools (written in C using htslib) for manipulating next-generation sequencing data","fork":true,"url":"https://api.github.com/repos/smowton/samtools","forks_url":"https://api.github.com/repos/smowton/samtools/forks","keys_url":"https://api.github.com/repos/smowton/samtools/keys{/key_id}","collaborators_url":"https://api.github.com/repos/smowton/samtools/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/smowton/samtools/teams","hooks_url":"https://api.github.com/repos/smowton/samtools/hooks","issue_events_url":"https://api.github.com/repos/smowton/samtools/issues/events{/number}","events_url":"https://api.github.com/repos/smowton/samtools/events","assignees_url":"https://api.github.com/repos/smowton/samtools/assignees{/user}","branches_url":"https://api.github.com/repos/smowton/samtools/branches{/branch}","tags_url":"https://api.github.com/repos/smowton/samtools/tags","blobs_url":"https://api.github.com/repos/smowton/samtools/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/smowton/samtools/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/smowton/samtools/git/refs{/sha}","trees_url":"https://api.github.com/repos/smowton/samtools/git/trees{/sha}","statuses_url":"https://api.github.com/repos/smowton/samtools/statuses/{sha}","languages_url":"https://api.github.com/repos/smowton/samtools/languages","stargazers_url":"https://api.github.com/repos/smowton/samtools/stargazers","contributors_url":"https://api.github.com/repos/smowton/samtools/contributors","subscribers_url":"https://api.github.com/repos/smowton/samtools/subscribers","subscription_url":"https://api.github.com/repos/smowton/samtools/subscription","commits_url":"https://api.github.com/repos/smowton/samtools/commits{/sha}","git_commits_url":"https://api.github.com/repos/smowton/samtools/git/commits{/sha}","comments_url":"https://api.github.com/repos/smowton/samtools/comments{/number}","issue_comment_url":"https://api.github.com/repos/smowton/samtools/issues/comments{/number}","contents_url":"https://api.github.com/repos/smowton/samtools/contents/{+path}","compare_url":"https://api.github.com/repos/smowton/samtools/compare/{base}...{head}","merges_url":"https://api.github.com/repos/smowton/samtools/merges","archive_url":"https://api.github.com/repos/smowton/samtools/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/smowton/samtools/downloads","issues_url":"https://api.github.com/repos/smowton/samtools/issues{/number}","pulls_url":"https://api.github.com/repos/smowton/samtools/pulls{/number}","milestones_url":"https://api.github.com/repos/smowton/samtools/milestones{/number}","notifications_url":"https://api.github.com/repos/smowton/samtools/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/smowton/samtools/labels{/name}","releases_url":"https://api.github.com/repos/smowton/samtools/releases{/id}","created_at":"2014-12-11T18:26:04Z","updated_at":"2014-12-11T18:26:08Z","pushed_at":"2015-07-01T15:44:15Z","git_url":"git://github.com/smowton/samtools.git","ssh_url":"git@github.com:smowton/samtools.git","clone_url":"https://github.com/smowton/samtools.git","svn_url":"https://github.com/smowton/samtools","homepage":"http://samtools.sourceforge.net/","size":9476,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"develop"}},"base":{"label":"samtools:develop","ref":"develop","sha":"b1a5854518649e665f8abba97d42f17e28b1bad9","user":{"login":"samtools","id":1518450,"avatar_url":"https://avatars.githubusercontent.com/u/1518450?v=3","gravatar_id":"","url":"https://api.github.com/users/samtools","html_url":"https://github.com/samtools","followers_url":"https://api.github.com/users/samtools/followers","following_url":"https://api.github.com/users/samtools/following{/other_user}","gists_url":"https://api.github.com/users/samtools/gists{/gist_id}","starred_url":"https://api.github.com/users/samtools/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/samtools/subscriptions","organizations_url":"https://api.github.com/users/samtools/orgs","repos_url":"https://api.github.com/users/samtools/repos","events_url":"https://api.github.com/users/samtools/events{/privacy}","received_events_url":"https://api.github.com/users/samtools/received_events","type":"Organization","site_admin":false},"repo":{"id":3666841,"name":"samtools","full_name":"samtools/samtools","owner":{"login":"samtools","id":1518450,"avatar_url":"https://avatars.githubusercontent.com/u/1518450?v=3","gravatar_id":"","url":"https://api.github.com/users/samtools","html_url":"https://github.com/samtools","followers_url":"https://api.github.com/users/samtools/followers","following_url":"https://api.github.com/users/samtools/following{/other_user}","gists_url":"https://api.github.com/users/samtools/gists{/gist_id}","starred_url":"https://api.github.com/users/samtools/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/samtools/subscriptions","organizations_url":"https://api.github.com/users/samtools/orgs","repos_url":"https://api.github.com/users/samtools/repos","events_url":"https://api.github.com/users/samtools/events{/privacy}","received_events_url":"https://api.github.com/users/samtools/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/samtools/samtools","description":"Tools (written in C using htslib) for manipulating next-generation sequencing data","fork":false,"url":"https://api.github.com/repos/samtools/samtools","forks_url":"https://api.github.com/repos/samtools/samtools/forks","keys_url":"https://api.github.com/repos/samtools/samtools/keys{/key_id}","collaborators_url":"https://api.github.com/repos/samtools/samtools/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/samtools/samtools/teams","hooks_url":"https://api.github.com/repos/samtools/samtools/hooks","issue_events_url":"https://api.github.com/repos/samtools/samtools/issues/events{/number}","events_url":"https://api.github.com/repos/samtools/samtools/events","assignees_url":"https://api.github.com/repos/samtools/samtools/assignees{/user}","branches_url":"https://api.github.com/repos/samtools/samtools/branches{/branch}","tags_url":"https://api.github.com/repos/samtools/samtools/tags","blobs_url":"https://api.github.com/repos/samtools/samtools/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/samtools/samtools/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/samtools/samtools/git/refs{/sha}","trees_url":"https://api.github.com/repos/samtools/samtools/git/trees{/sha}","statuses_url":"https://api.github.com/repos/samtools/samtools/statuses/{sha}","languages_url":"https://api.github.com/repos/samtools/samtools/languages","stargazers_url":"https://api.github.com/repos/samtools/samtools/stargazers","contributors_url":"https://api.github.com/repos/samtools/samtools/contributors","subscribers_url":"https://api.github.com/repos/samtools/samtools/subscribers","subscription_url":"https://api.github.com/repos/samtools/samtools/subscription","commits_url":"https://api.github.com/repos/samtools/samtools/commits{/sha}","git_commits_url":"https://api.github.com/repos/samtools/samtools/git/commits{/sha}","comments_url":"https://api.github.com/repos/samtools/samtools/comments{/number}","issue_comment_url":"https://api.github.com/repos/samtools/samtools/issues/comments{/number}","contents_url":"https://api.github.com/repos/samtools/samtools/contents/{+path}","compare_url":"https://api.github.com/repos/samtools/samtools/compare/{base}...{head}","merges_url":"https://api.github.com/repos/samtools/samtools/merges","archive_url":"https://api.github.com/repos/samtools/samtools/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/samtools/samtools/downloads","issues_url":"https://api.github.com/repos/samtools/samtools/issues{/number}","pulls_url":"https://api.github.com/repos/samtools/samtools/pulls{/number}","milestones_url":"https://api.github.com/repos/samtools/samtools/milestones{/number}","notifications_url":"https://api.github.com/repos/samtools/samtools/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/samtools/samtools/labels{/name}","releases_url":"https://api.github.com/repos/samtools/samtools/releases{/id}","created_at":"2012-03-09T02:49:58Z","updated_at":"2015-08-19T21:10:06Z","pushed_at":"2015-08-20T13:51:08Z","git_url":"git://github.com/samtools/samtools.git","ssh_url":"git@github.com:samtools/samtools.git","clone_url":"https://github.com/samtools/samtools.git","svn_url":"https://github.com/samtools/samtools","homepage":"http://samtools.sourceforge.net/","size":14299,"stargazers_count":279,"watchers_count":279,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":174,"mirror_url":null,"open_issues_count":132,"forks":174,"open_issues":132,"watchers":279,"default_branch":"develop"}},"_links":{"self":{"href":"https://api.github.com/repos/samtools/samtools/pulls/419"},"html":{"href":"https://github.com/samtools/samtools/pull/419"},"issue":{"href":"https://api.github.com/repos/samtools/samtools/issues/419"},"comments":{"href":"https://api.github.com/repos/samtools/samtools/issues/419/comments"},"review_comments":{"href":"https://api.github.com/repos/samtools/samtools/pulls/419/comments"},"review_comment":{"href":"https://api.github.com/repos/samtools/samtools/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/samtools/samtools/pulls/419/commits"},"statuses":{"href":"https://api.github.com/repos/samtools/samtools/statuses/a1814030f5a843e62619c61b3ffe857688e5d41e"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"login":"jmarshall","id":70921,"avatar_url":"https://avatars.githubusercontent.com/u/70921?v=3","gravatar_id":"","url":"https://api.github.com/users/jmarshall","html_url":"https://github.com/jmarshall","followers_url":"https://api.github.com/users/jmarshall/followers","following_url":"https://api.github.com/users/jmarshall/following{/other_user}","gists_url":"https://api.github.com/users/jmarshall/gists{/gist_id}","starred_url":"https://api.github.com/users/jmarshall/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmarshall/subscriptions","organizations_url":"https://api.github.com/users/jmarshall/orgs","repos_url":"https://api.github.com/users/jmarshall/repos","events_url":"https://api.github.com/users/jmarshall/events{/privacy}","received_events_url":"https://api.github.com/users/jmarshall/received_events","type":"User","site_admin":false},"comments":4,"review_comments":0,"commits":2,"additions":131,"deletions":40,"changed_files":1}}