{"action":"created","issue":{"url":"https://api.github.com/repos/PistonDevelopers/conrod/issues/467","labels_url":"https://api.github.com/repos/PistonDevelopers/conrod/issues/467/labels{/name}","comments_url":"https://api.github.com/repos/PistonDevelopers/conrod/issues/467/comments","events_url":"https://api.github.com/repos/PistonDevelopers/conrod/issues/467/events","html_url":"https://github.com/PistonDevelopers/conrod/issues/467","id":83671433,"number":467,"title":"Probabilistic algorithm for hierarchial ids","user":{"login":"bvssvni","id":1743862,"avatar_url":"https://avatars.githubusercontent.com/u/1743862?v=3","gravatar_id":"","url":"https://api.github.com/users/bvssvni","html_url":"https://github.com/bvssvni","followers_url":"https://api.github.com/users/bvssvni/followers","following_url":"https://api.github.com/users/bvssvni/following{/other_user}","gists_url":"https://api.github.com/users/bvssvni/gists{/gist_id}","starred_url":"https://api.github.com/users/bvssvni/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bvssvni/subscriptions","organizations_url":"https://api.github.com/users/bvssvni/orgs","repos_url":"https://api.github.com/users/bvssvni/repos","events_url":"https://api.github.com/users/bvssvni/events{/privacy}","received_events_url":"https://api.github.com/users/bvssvni/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/PistonDevelopers/conrod/labels/information","name":"information","color":"207de5"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-06-01T20:08:26Z","updated_at":"2015-06-03T09:44:33Z","closed_at":null,"body":"The idea is to support both incremental ids and reserved ids. An id is `u64` which has 18446744073709552000 ids to pick from. If we split this space into chunks of a million or ten millions, then we can pick a random number multiplied with the chunks size to get a probabilistic unique parent id. This makes it possible to \"reserve\" a space of widget ids.\r\n\r\nAssuming that no application needs more than 100 000 parents, we can compute the probability of id collision:\r\n\r\n```\r\nu64_space=18446744073709552000\r\nchunk_size=10_000_000\r\nrandom_space=u64_space/chunk_size\r\nparents=100_000\r\n1-(1-1/random_space)^parents = 5.42e-8\r\n```\r\n\r\nWe can also use an id as the seed to the random number generator, so we get deterministically reservation of new chunks in a hierarchy."},"comment":{"url":"https://api.github.com/repos/PistonDevelopers/conrod/issues/comments/108274580","html_url":"https://github.com/PistonDevelopers/conrod/issues/467#issuecomment-108274580","issue_url":"https://api.github.com/repos/PistonDevelopers/conrod/issues/467","id":108274580,"user":{"login":"bvssvni","id":1743862,"avatar_url":"https://avatars.githubusercontent.com/u/1743862?v=3","gravatar_id":"","url":"https://api.github.com/users/bvssvni","html_url":"https://github.com/bvssvni","followers_url":"https://api.github.com/users/bvssvni/followers","following_url":"https://api.github.com/users/bvssvni/following{/other_user}","gists_url":"https://api.github.com/users/bvssvni/gists{/gist_id}","starred_url":"https://api.github.com/users/bvssvni/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bvssvni/subscriptions","organizations_url":"https://api.github.com/users/bvssvni/orgs","repos_url":"https://api.github.com/users/bvssvni/repos","events_url":"https://api.github.com/users/bvssvni/events{/privacy}","received_events_url":"https://api.github.com/users/bvssvni/received_events","type":"User","site_admin":false},"created_at":"2015-06-03T09:44:33Z","updated_at":"2015-06-03T09:44:33Z","body":"### Semantics\r\n\r\nYou have an arbitrary deterministic algorithm that generates numbers, where the numbers describe an arbitrary tree structure through two operations `increment` and `reserve`. The tree structure is decided by the algorithm alone, and the same seed give the same tree structure. A different seed generates the same shape of tree structure but different numbers.\r\n\r\nThe number has the properties that any receiver of the entire list of numbers with the same random generator can replicate the choices made by the algorithm. This is because `increment` is trivial and `reserve` depends on one of the earlier numbers. When a number appears that is not incremented from an earlier number, the receiver can try reserving using all the earlier numbers to find which number is the parent of the new number. Finding the parent of a new number given `N` numbers is `O(N)`. Finding children is `O(1)`.\r\n\r\nIt gets funnier when the algorithm (Alice) has a hidden internal state and communicates with receiver (Bob). Alice sends data to Bob, and assigns each piece of data with a number. Each time the Alice works, she can decide to send different pieces. A piece of data is no longer needed when it has no parent. Alice can choose to `overwrite` or `modify` data at will, but does not keep track of when data must be garbage collected. If Alice touches all data needed each time she works, then Bob can use a sweep garbage collector by checking if each piece of data was accessed. If Alice can tell Bob which parents to keep, then Bob only needs to sweep through parts of the data avoiding the branches that are unchanged, and Alice only need to work with the data that changes.\r\n\r\nThis is quite a bit similar to the memory model of Rust where all data has an owner, but the difference is that the relations are procedurally generated by an algorithm. The data structure is never stored, only the pieces to maintain the state between each interaction with the internal state of the algorithm. The algorithm is free to change its behavior over time, and the memory no longer needed can be freed without the algorithm explicitly telling what needs to be freed. If the algorithm can determine that a part of itself results deterministically in the same output as before, it can reuse that branch of the results.\r\n\r\nSo, you can have an immediate mode design for changing data mixed with retained mode design for the unchanged data."}}