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.
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.