SPOP optional count argument. #1793

Closed
antirez opened this Issue Jun 3, 2014 · 2 comments

Comments

Projects
None yet
3 participants
@antirez
Owner

antirez commented Jun 3, 2014

Having an optional count in SPOP could be a good idea, so that when the variant with three arguments is called, SPOP would return an array instead of a single value, populated with the specified number of elements (assuming there are enough elements).

Redis 3.2 thing, so for now what is needed to go forward is feedbacks, and comparisons with SRANDMEMBER command documented here.

Example use case

Modeling a web-based game of poker. Populate your deck, and provide 5 cards to every player with SPOP key 5 instead of calling SPOP 5 times. The same pattern can be applied to different deck-card-alike problems.

Example call and output

> SPOP mylist 5
1) 3
2) 5
3) 10
4) 7
5) 6

Edge cases

When the set is short on elements (cardinality < count), probably it makes sense to return as much elements as possible. The behavior with non existing keys would be to return an empty array, like LRANGE does in similar conditions, but for lists.

Change of return value

There is the argument about a command changing return value from string to array when an additional argument is given, so actually the following two commands would provide different results:

  • SPOP key
  • SPOP key 1

Both return 1 element, but the second in form of an array. However I think it is straightforward to see the second case as just a special case of the array form, so no confusion should arise. Note: this already happens with SRANDMEMBER, SET, `SORT. So we have a green light for existing API, but in general the rationale is that, as long as the command signature changes, it is ok to change the return value. What we want to avoid is for example, that in a variadic command one argument or three will change the return value, or that a specific value of an argument changes the return value: both cases create problems when generating command arguments programmatically.

@antirez antirez added this to the Redis >= 3.2 milestone Jun 3, 2014

@michael-grunder

This comment has been minimized.

Show comment
Hide comment
@michael-grunder

michael-grunder Jun 3, 2014

Contributor

I don't personally use SPOP at all but the multiple return types is trivial to implement in a client, so sounds good to me.

Contributor

michael-grunder commented Jun 3, 2014

I don't personally use SPOP at all but the multiple return types is trivial to implement in a client, so sounds good to me.

@advance512

This comment has been minimized.

Show comment
Hide comment
@advance512

advance512 Jun 9, 2014

Contributor

I implemented this feature here, based on the latest 3.0 commit:
advance512@7ad7d25
(in my fork:
https://github.com/advance512/redis/tree/spopWithCount)

Some notes:

  1. I added a intsetRandomMembers() function for better performance (instead of calling intsetRandomMember() COUNT-times). I implemented two different algorithms for getting random members, and the best one is chosen in run-time depending on the ratio between the intset size and the requested result size. (The threshold ratio currently is 2, I want to perf test it and see where the sweet spot lies.)
  2. I added a setTypeRandomElements() function that uses intsetRandomMembers() or dictGetRandomKeys() to populate a set with random elements. It is fairly optimized.
  3. spopWithCountCommand() uses setTypeRandomElements() to read the elements into a set, then output them into a bulk reply.
  4. I return an empty multibulk when COUNT=0 or the set doesn't exist. (Edge case detailed above.)
  5. AOF/replication/notifications work as before.
  6. Randomness isn't very good, and SPOP with COUNT isn't suitable for use cases where a good distribution is required.
  7. I added new tests. They all pass.

As I write this, I realize that [ SPOP key 1 ] runs spopWithCountCommand() while [ SPOP key ] runs spopCommand(). Results should be identical (empty bulk result or bulk result with 1 item), but perhaps I should call the old spopCommand() if COUNT==1.

Please have a look and let me know what you think.

Contributor

advance512 commented Jun 9, 2014

I implemented this feature here, based on the latest 3.0 commit:
advance512@7ad7d25
(in my fork:
https://github.com/advance512/redis/tree/spopWithCount)

Some notes:

  1. I added a intsetRandomMembers() function for better performance (instead of calling intsetRandomMember() COUNT-times). I implemented two different algorithms for getting random members, and the best one is chosen in run-time depending on the ratio between the intset size and the requested result size. (The threshold ratio currently is 2, I want to perf test it and see where the sweet spot lies.)
  2. I added a setTypeRandomElements() function that uses intsetRandomMembers() or dictGetRandomKeys() to populate a set with random elements. It is fairly optimized.
  3. spopWithCountCommand() uses setTypeRandomElements() to read the elements into a set, then output them into a bulk reply.
  4. I return an empty multibulk when COUNT=0 or the set doesn't exist. (Edge case detailed above.)
  5. AOF/replication/notifications work as before.
  6. Randomness isn't very good, and SPOP with COUNT isn't suitable for use cases where a good distribution is required.
  7. I added new tests. They all pass.

As I write this, I realize that [ SPOP key 1 ] runs spopWithCountCommand() while [ SPOP key ] runs spopCommand(). Results should be identical (empty bulk result or bulk result with 1 item), but perhaps I should call the old spopCommand() if COUNT==1.

Please have a look and let me know what you think.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment