{"action":"created","issue":{"url":"https://api.github.com/repos/pcbend/GRSISort/issues/205","labels_url":"https://api.github.com/repos/pcbend/GRSISort/issues/205/labels{/name}","comments_url":"https://api.github.com/repos/pcbend/GRSISort/issues/205/comments","events_url":"https://api.github.com/repos/pcbend/GRSISort/issues/205/events","html_url":"https://github.com/pcbend/GRSISort/issues/205","id":58509883,"number":205,"title":"Pre-Sorting of Fragment Tree","user":{"login":"VinzenzBildstein","id":7277216,"avatar_url":"https://avatars.githubusercontent.com/u/7277216?v=3","gravatar_id":"","url":"https://api.github.com/users/VinzenzBildstein","html_url":"https://github.com/VinzenzBildstein","followers_url":"https://api.github.com/users/VinzenzBildstein/followers","following_url":"https://api.github.com/users/VinzenzBildstein/following{/other_user}","gists_url":"https://api.github.com/users/VinzenzBildstein/gists{/gist_id}","starred_url":"https://api.github.com/users/VinzenzBildstein/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/VinzenzBildstein/subscriptions","organizations_url":"https://api.github.com/users/VinzenzBildstein/orgs","repos_url":"https://api.github.com/users/VinzenzBildstein/repos","events_url":"https://api.github.com/users/VinzenzBildstein/events{/privacy}","received_events_url":"https://api.github.com/users/VinzenzBildstein/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/pcbend/GRSISort/milestones/2","html_url":"https://github.com/pcbend/GRSISort/milestones/Time%20Ordered%20Writing","labels_url":"https://api.github.com/repos/pcbend/GRSISort/milestones/2/labels","id":1006173,"number":2,"title":"Time Ordered Writing","description":"","creator":{"login":"r3dunlop","id":5428160,"avatar_url":"https://avatars.githubusercontent.com/u/5428160?v=3","gravatar_id":"","url":"https://api.github.com/users/r3dunlop","html_url":"https://github.com/r3dunlop","followers_url":"https://api.github.com/users/r3dunlop/followers","following_url":"https://api.github.com/users/r3dunlop/following{/other_user}","gists_url":"https://api.github.com/users/r3dunlop/gists{/gist_id}","starred_url":"https://api.github.com/users/r3dunlop/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/r3dunlop/subscriptions","organizations_url":"https://api.github.com/users/r3dunlop/orgs","repos_url":"https://api.github.com/users/r3dunlop/repos","events_url":"https://api.github.com/users/r3dunlop/events{/privacy}","received_events_url":"https://api.github.com/users/r3dunlop/received_events","type":"User","site_admin":false},"open_issues":3,"closed_issues":2,"state":"open","created_at":"2015-03-04T17:34:58Z","updated_at":"2015-03-19T16:10:19Z","due_on":null,"closed_at":null},"comments":20,"created_at":"2015-02-22T17:13:27Z","updated_at":"2015-03-26T22:37:10Z","closed_at":null,"body":"Ryan and I have been discussing the issue of the \"random\" reading we do on the trees when we sort them by timestamp and how long that takes.\r\nWe've found a post by Axel on the root-forum stating that the trees are good for sequential forward access (also jumping a number of entries forward), but not random access.\r\nTo check this I wrote to a root file a simple tree with two doubles as branches. Each branch was filled with rand() and the tree has a total of 100 million entries (the root file got 1010 MBytes big).\r\nThen I wrote a simple program that first went through the tree and read it sequentially, then created an index and sorted through that index.\r\nSince the last step took so long I reduced it to read only 10000 entries.\r\nThese are the timing results:\r\nReading 100000000 sequentially took 17.9161 seconds.\r\nSorting 100000000 took 81.2872 seconds.\r\nReading     10000 'randomly' took 461.48 seconds.\r\n\r\nThe next step was to write a tree with the same two doubles, but instead of setting each to rand() I set them to i+rand()/2147483, this way they are at most out of order by 1000 entries.\r\nFor this tree the results are:\r\nReading 10000000 sequentially took 1.70509 seconds.\r\nSorting 10000000 took 3.32832 seconds.\r\nReading 10000000 'randomly' took 354.002 seconds.\r\nSo the random reading goes faster if the data is semi-sorted (like our data is).\r\n\r\nThe next test was to create a simple class containing the same two doubles as members and filling a tree with this class (semi-ordered as before).\r\nFor this tree I got:\r\nReading 10000000 sequentially took 4.25989 seconds.\r\nSorting 10000000 took 5.15294 seconds.\r\nReading 10000000 'randomly' took 524.221 seconds.\r\nReading and sorting 10000000 took 19.7562 seconds.\r\nThe last step (Reading and sorting) reads the entries sequentially and puts them into a multiset (without doing anything else with them). I've compiled all these tests without any optimization, so my hope is that this is the actual time it takes to sort the data using a multiset.\r\n\r\nTo me this means that pre-sorting our FragmentTree (before we write it) is the way to go as it saves a ton of time later on, even if we only create the analysis-tree once. One way to do this is to simply change the TFragmentQueue to use a std::multiset instead of a std::queue, with comparison operators that depend on whether it's Griffin or Tigress data.\r\nWe could also think about adding a flag that enables pre-sorting, so that without that flag we use the normal std::queue, but that would require a few if-statements upon filling and reading from the queue. And since the above test seems to show that we'll always want to run with pre-sorting as long as the input data isn't sorted, we would only need to change the code back to not pre-sort once the DAQ is fixed so that we get sorted data.\r\n\r\nP.S.:\r\nI've also checked how long it takes to write this tree (including opening the root-file and creating the tree itself):\r\nWriting 10 000 000 events took 12.4989 seconds.\r\nThis gives a 99 MB file, so a write-speed of about 8 MB/s which isn't very good, considering that our raid performs at 500MB/s during a bonnie test.\r\nWriting the simple tree with two doubles as branches, 100 000 000 events (504 MB) take 54.3706 seconds, i.e. 9 MB/s. So the problem doesn't seem to be writing a class, but even simple doubles take forever to write with root.\r\n"},"comment":{"url":"https://api.github.com/repos/pcbend/GRSISort/issues/comments/86742376","html_url":"https://github.com/pcbend/GRSISort/issues/205#issuecomment-86742376","issue_url":"https://api.github.com/repos/pcbend/GRSISort/issues/205","id":86742376,"user":{"login":"r3dunlop","id":5428160,"avatar_url":"https://avatars.githubusercontent.com/u/5428160?v=3","gravatar_id":"","url":"https://api.github.com/users/r3dunlop","html_url":"https://github.com/r3dunlop","followers_url":"https://api.github.com/users/r3dunlop/followers","following_url":"https://api.github.com/users/r3dunlop/following{/other_user}","gists_url":"https://api.github.com/users/r3dunlop/gists{/gist_id}","starred_url":"https://api.github.com/users/r3dunlop/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/r3dunlop/subscriptions","organizations_url":"https://api.github.com/users/r3dunlop/orgs","repos_url":"https://api.github.com/users/r3dunlop/repos","events_url":"https://api.github.com/users/r3dunlop/events{/privacy}","received_events_url":"https://api.github.com/users/r3dunlop/received_events","type":"User","site_admin":false},"created_at":"2015-03-26T22:37:10Z","updated_at":"2015-03-26T22:37:10Z","body":"I should also point out something Greg mentioned to me. He said that he tried running the sort code on Carl's laptop, and it ran 3 times faster then when ran on nessa (here at Guelph). The only conclusion that can be drawn from this is that having an SSD hard drive was the reason. This might mean root is writing in smaller blocks than we think. I think we are going to need to find a combination of memfiles and parallelizing to solve this problem."}}