YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Container Performance

Get Embed Code
13 Languages

Showing Revision 4 created 05/25/2016 by Udacity Robot.

  1. So we've talked about how your code
    could be slow because the type of

  2. hardware that's executing underneath it,
  3. remember the whole floating
    point branching issue problem?
  4. Well, that's mostly a non-issue for
    today's hardware.
  5. There's one set of issues that you
    still need to worry about, that is,
  6. the performance of the primitives
    in the language that you are using.
  7. Take a fundamental
    algorithm such as sorting.
  8. Now there are many
    ways in which to sort,
  9. and some are better than others,
    depending on the circumstances.
  10. For examples, quicksort is generally
  11. faster than bubble sort except when you
    have a fewer than a thousand elements or
  12. take searching for
    objects in a large sorted list.
  13. Generally, the best way to do
    this is with a binary search.
  14. But completely different is finding
    objects in an unsorted array.
  15. Now instead of in comparing each object
    for the value you're looking for,
  16. you can use a hash function
    to find it immediately.
  17. Now this is all basic canon of modern
    computer science and data structures.
  18. And thankfully, modern languages like
    Java supply these containers and
  19. algorithms on your behalf, so that
    you don't have to rewrite the Murmur
  20. 3 Hash function or a quicksort over and
    over and over again.
  21. But let me reveal something here.
  22. In all of my years of programming,
  23. the one problem that consistently
    bites performance of your project
  24. has to do with the performance of these
    language-provided container objects.
  25. I mean, it's awesome, right?
  26. Java's providing you with
    an implementation of a vector class that
  27. you can push, pop, add, and
    remove objects as you see fit, but
  28. in order to get that flexibility, it has
    to use a linked list structure under
  29. the hood, which has a unique set
    of performance characteristics.
  30. As long as you are only operating on
    the front of the list, it's super fast.
  31. But if you're trying to insert or
  32. remove in other places, it's going to
    default to the worst possible time.
  33. The point is that just because
    the underlying system provides
  34. these containers doesn't mean
    that they're performant with
  35. respect to how your program is
    going to actually be using them.
  36. James Sutherland published a series of
    microbenchmarks on the performance of
  37. specific data structures provided
    by the Java framework and
  38. found that there's some differences
    in performance versus functionality
  39. that people need to be aware of.
  40. For example,
    he found that Hashtable performance
  41. was about 22% faster
    than HashMap performance,
  42. depending on how you're actually
    using the containers themselves.
  43. The point is this.
  44. Have you profiled your container
    classes that you're using in your code?
  45. Are you confident that they are using
    the absolute fastest container for
  46. what your code is actually doing?
  47. Mm, yeah, that's what I thought.
  48. But the good news is that you can gain
    visibility into the performance of these
  49. containers with some handy
    profiling MPIs in Android.
  50. So let's see if Chris's code
    stands up to our scrutiny.