Pretty sure that would be computationally intractable. Every time someone was upvoted beyond a threshhold youâd need to check the data of every comment and post on the forum.
Someone I know has worked with databases of varying sizes, sometimes in a low level, mechanical sense . From my understanding, to update all of a personâs votes, the database operation is pretty simple, simply scanning the voting table for that ID and then doing a little arithmetic for each upvote and calling another table or two.
You would only need to do the above operation for each ânewly promotedâ user, which is like maybe a few dozen users a day at the worst.
Many personal projects involve heavier operations. Iâm not sure but a google search might be 100x more complicated.
But in the process you might also promote other usersâso youâd have to check for each recipient of strong upvotes if that was so, and then repeat the process for each promoted user, and so on.
Thatâs a really good point. Thereâs many consequent issues beyond the initial update, including the iterative issue of multiple induced ârounds of updatingâ mentioned in your comment.
After some thought, I think I am confident the issue you mentioned is small.
First, note that there is an end point to this process, eg a âfixed pointâ that the rounds stop.
Based on some guesses, the second and subsequent round of promotions gets much much smaller in number of people affected (as opposed to a process that explodes). This is because the karma and vote power schedule has huge karma intervals between ranks ,compared to the per account karma increase from this process. Also these intervals greatly increase as rank increases (something something concavity) .
To be confident, I guess that these second round and after computations are probably <<50% of the initial first round computational cost.
Finally, if the above wasnât true and the increased costs were ridiculous (1000x or something) you could just batch this, say, every day, and defer updates in advanced rounds to later batches. This isnât the same result, as you permanently have this sort of queue, but I guess itâs a 90% good solution.
Iâm confident but at the same time LARPing here and would be happy if an actual CS person corrected me.
[Iâm not a computer scientist, but] Charles is right. The backend engineering for this wonât be trivial, but it isnât hard either.
The algorithmic difficulty seems roughly on the level of what Iâd expect a typical software engineering interview in a Silicon Valley tech company to look like, maybe a little easier, though of course the practical implementation might be much more difficult if you want to account for all of the edge cases in the actual code and database.
The computational costs is likely trivial in comparison. Like itâs mathematically equivalent to if every newly promoted user just unupvoted and reupvoted again. On net youâre looking at an at-most 2x increase in the load on the upvote system, which I expect to be a tiny increase in total computational costs, assuming that the codebase has an okay design.
To be clear, Iâm looking at the computational costs, not algorithmic complexity which I agree isnât huge.
Where are you getting 2x from for computations? If User A has cast strong upvotes to up to N different people, each of who has cast strong upvotes to up to N different people, and so on up to depth D, then naively a promotion for A seems to have O(N^D) operations, as opposed to O(1) for the current algorithm. (though maybe D is a function of N?)
In practice as Charles says big O is probably giving a very pessimistic view here since thereâs a large gap between most ranks, so maybe itâs workableâthough if a lot of the forumâs users are new (eg if forum use grows exponentially for a while, or if users cycle over time) then you could have a large proportion of users in the first three ranks, ie being relatively likely to be promoted by a given karma increase.
I retract the <2x claim. I think itâs still basically correct, but I canât prove it so there may well be edge cases Iâm missing.
My new claim is <=16x.
We currently have a total of U upvotes. The maximal karma threshold is 16 karma per strong upvote at 500k karma (and there are no fractional karma). So the âworst caseâ scenario is if all current users are at the lowest threshold (<10 karma) and you top out at making all users >500k karma, with 16 loops across all upvotes. This involves ~16U updates, which is bounded at 16x.
If you do all the changes at once you might crash a server, but presumably itâs not very hard to queue and amortize.
I think youâre mixing up updates and operations. If I understand you right, youâre saying each user on the forum can get promoted at most 16 times, so at most each strong update gets incremented 16 times.
But you have to count the operations of the algorithm that does that. My naive effort is something like this: Each time a userâs rank updates (1 operation), you have to find and update all the posts and users that received their strong upvotes (~N operations where N is either their number of strong upvotes, or their number of votes depending on how the data is stored). For each of those postsâ users, you now need to potentially do the same again (N^2 operations in the worst case) and so on.
(Using big O approach of worst case after ignoring constants)
The exponent probably couldnât get that highâeg maybe you could prove no cascade would cause a user to be promoted more than once in practice (eg each karma threshold is >2x the previous, so if a user was one karma short of it, and all their karma was in strong upvotes, then at most their karma could double unless someone else was somehow multiply promoted), so I was probably wrong that itâs computationally intractable. I do think it could plausibly impose a substantial computational burden on a tiny operation like CEA though, so itâd be someone would need to do the calculations carefully before trying to implement it.
Thereâs also the philosophical question of whether itâs a good ideaâif we think increasing karma is a proxy for revealing good judgement, then we might want to retroactively reward users for upvotes from higher ranked people. If we think itâs more like a proxy for developing good judgement, then maybe the promoteeâs earlier upvotes shouldnât carry any increased weight, or at least not as much.
Maybe we should automatically update upvotes to track peopleâs current karma?
Pretty sure that would be computationally intractable. Every time someone was upvoted beyond a threshhold youâd need to check the data of every comment and post on the forum.
Someone I know has worked with databases of varying sizes, sometimes in a low level, mechanical sense . From my understanding, to update all of a personâs votes, the database operation is pretty simple, simply scanning the voting table for that ID and then doing a little arithmetic for each upvote and calling another table or two.
You would only need to do the above operation for each ânewly promotedâ user, which is like maybe a few dozen users a day at the worst.
Many personal projects involve heavier operations. Iâm not sure but a google search might be 100x more complicated.
But in the process you might also promote other usersâso youâd have to check for each recipient of strong upvotes if that was so, and then repeat the process for each promoted user, and so on.
Thatâs a really good point. Thereâs many consequent issues beyond the initial update, including the iterative issue of multiple induced ârounds of updatingâ mentioned in your comment.
After some thought, I think I am confident the issue you mentioned is small.
First, note that there is an end point to this process, eg a âfixed pointâ that the rounds stop.
Based on some guesses, the second and subsequent round of promotions gets much much smaller in number of people affected (as opposed to a process that explodes). This is because the karma and vote power schedule has huge karma intervals between ranks ,compared to the per account karma increase from this process. Also these intervals greatly increase as rank increases (something something concavity) .
To be confident, I guess that these second round and after computations are probably <<50% of the initial first round computational cost.
Finally, if the above wasnât true and the increased costs were ridiculous (1000x or something) you could just batch this, say, every day, and defer updates in advanced rounds to later batches. This isnât the same result, as you permanently have this sort of queue, but I guess itâs a 90% good solution.
Iâm confident but at the same time LARPing here and would be happy if an actual CS person corrected me.
[Iâm not a computer scientist, but] Charles is right. The backend engineering for this wonât be trivial, but it isnât hard either.
The algorithmic difficulty seems roughly on the level of what Iâd expect a typical software engineering interview in a Silicon Valley tech company to look like, maybe a little easier, though of course the practical implementation might be much more difficult if you want to account for all of the edge cases in the actual code and database.
The computational costs is likely trivial in comparison. Like itâs mathematically equivalent to if every newly promoted user just unupvoted and reupvoted again. On net youâre looking at an at-most 2x increase in the load on the upvote system, which I expect to be a tiny increase in total computational costs, assuming that the codebase has an okay design.
To be clear, Iâm looking at the computational costs, not algorithmic complexity which I agree isnât huge.
Where are you getting 2x from for computations? If User A has cast strong upvotes to up to N different people, each of who has cast strong upvotes to up to N different people, and so on up to depth D, then naively a promotion for A seems to have O(N^D) operations, as opposed to O(1) for the current algorithm. (though maybe D is a function of N?)
In practice as Charles says big O is probably giving a very pessimistic view here since thereâs a large gap between most ranks, so maybe itâs workableâthough if a lot of the forumâs users are new (eg if forum use grows exponentially for a while, or if users cycle over time) then you could have a large proportion of users in the first three ranks, ie being relatively likely to be promoted by a given karma increase.
I retract the <2x claim. I think itâs still basically correct, but I canât prove it so there may well be edge cases Iâm missing.
My new claim is <=16x.
We currently have a total of U upvotes. The maximal karma threshold is 16 karma per strong upvote at 500k karma (and there are no fractional karma). So the âworst caseâ scenario is if all current users are at the lowest threshold (<10 karma) and you top out at making all users >500k karma, with 16 loops across all upvotes. This involves ~16U updates, which is bounded at 16x.
If you do all the changes at once you might crash a server, but presumably itâs not very hard to queue and amortize.
I think youâre mixing up updates and operations. If I understand you right, youâre saying each user on the forum can get promoted at most 16 times, so at most each strong update gets incremented 16 times.
But you have to count the operations of the algorithm that does that. My naive effort is something like this: Each time a userâs rank updates (1 operation), you have to find and update all the posts and users that received their strong upvotes (~N operations where N is either their number of strong upvotes, or their number of votes depending on how the data is stored). For each of those postsâ users, you now need to potentially do the same again (N^2 operations in the worst case) and so on.
(Using big O approach of worst case after ignoring constants)
The exponent probably couldnât get that highâeg maybe you could prove no cascade would cause a user to be promoted more than once in practice (eg each karma threshold is >2x the previous, so if a user was one karma short of it, and all their karma was in strong upvotes, then at most their karma could double unless someone else was somehow multiply promoted), so I was probably wrong that itâs computationally intractable. I do think it could plausibly impose a substantial computational burden on a tiny operation like CEA though, so itâd be someone would need to do the calculations carefully before trying to implement it.
Thereâs also the philosophical question of whether itâs a good ideaâif we think increasing karma is a proxy for revealing good judgement, then we might want to retroactively reward users for upvotes from higher ranked people. If we think itâs more like a proxy for developing good judgement, then maybe the promoteeâs earlier upvotes shouldnât carry any increased weight, or at least not as much.