How does List vs Tuple preformance work

Questions / Help
, , , ,
1

I heard that editing a tuple is a much more expensive operation then editing a list

i just don’t get the why, when a list is mutated a new list made in memory when edited, same as tuple; they use references from other variables and only really store the new values so it should both be fast. “the elements themselves are not copied. When you update a tuple, all entries are shared between the old and the new tuple, except for the entry that has been replaced” So I don’t even understand considering that previous statement the whole part about “a whole new tuple made in memory” it seems contradicting

And what does it matter if it’s contiguous If they are both in memory, isn’t basically every value like that, (Which is if I got the definition right just one place in memory, not fragmented)? Maybe not lists because of the whole linked thing but that is just a wild throw of a guess. I really don’t know :confused: I’m new to this stuff

So what actually is the difference with performance (considering all the factors mentioned before and others)? Thanks!

1 Like
2

I heard that editing a tuple is a much more expensive operation then editing a list

Are you sure you heard it that way and not the reverse?

Lists have very different performance characteristics depending on which section of the list you edit. Editing in the front is fine. Editing in the back a lot less so, given it’ll invalidate all preceeding cons cells. The values fill be fine, but the refences to the next cell need to be adjusted all the way from the front to the edited element.

3 Likes
3

I did a small benchmark that compares functions that exists for lists and for tuples. The source is here: Benchmarks of tuples vs lists · GitHub

Size is 100000 items.

Name                                           ips        average  deviation         median         99th %
list insert_at_start                      799.46 K        1.25 μs    ±56.90%        1.40 μs        1.47 μs
list delete_at_start                      763.82 K        1.31 μs  ±2526.28%        1.40 μs        1.47 μs
tuple delete_at_end                         6.54 K      152.85 μs    ±58.71%      118.17 μs      347.78 μs
tuple delete_at_start                       6.50 K      153.88 μs    ±57.49%      117.34 μs      352.52 μs
tuple delete_at_middle                      6.42 K      155.84 μs    ±58.16%      118.31 μs      381.88 μs
tuple delete_at_random_index                6.31 K      158.49 μs    ±59.24%      119.15 μs      411.01 μs
list insert_at_random_index                 6.21 K      161.13 μs    ±24.39%      156.79 μs      317.22 μs
list delete_at_random_index                 6.19 K      161.51 μs    ±18.80%      169.64 μs      197.02 μs
tuple insert_at_middle                      5.34 K      187.22 μs    ±71.53%      127.88 μs      660.99 μs
tuple insert_at_random_index                5.33 K      187.77 μs    ±70.21%      127.88 μs      659.84 μs
tuple insert_at_start                       5.33 K      187.77 μs    ±74.48%      123.48 μs      697.20 μs
tuple insert_at_end                         5.22 K      191.57 μs    ±73.29%      130.33 μs      735.98 μs
list insert_at_middle                       4.08 K      245.29 μs    ±27.99%      223.98 μs      492.32 μs
list sum                                    3.83 K      261.43 μs     ±8.54%      250.45 μs      315.83 μs
list to_tuple                               3.50 K      286.10 μs    ±46.85%      224.19 μs      701.57 μs
list product                                3.31 K      302.34 μs    ±20.24%      338.18 μs      353.47 μs
tuple random_replace                        2.59 K      386.77 μs    ±56.91%      407.75 μs     1144.39 μs
list delete_at_middle                       1.71 K      583.73 μs    ±30.48%      701.44 μs      920.59 μs
tuple sum                                   1.47 K      679.29 μs    ±51.47%      598.77 μs     2507.16 μs
tuple product                               1.44 K      694.17 μs    ±55.88%      548.48 μs     2409.10 μs
tuple to_list product                       1.24 K      807.42 μs    ±65.46%      511.67 μs     2191.66 μs
tuple to_list sum                           1.20 K      832.56 μs    ±70.15%      482.20 μs     2213.17 μs
list insert_at_end                          0.94 K     1061.78 μs    ±37.81%     1263.79 μs     1806.01 μs
tuple to_list                               0.78 K     1287.32 μs    ±79.96%      906.29 μs     4748.49 μs
list random_replace                         0.67 K     1496.43 μs    ±84.24%     1340.76 μs     6404.22 μs
list delete_at_end                          0.52 K     1920.07 μs    ±53.00%     1879.47 μs     4942.26 μs
list grow_prepend                           0.39 K     2538.98 μs    ±51.59%     2451.91 μs     6270.11 μs
list to_tuple random_replace to_list        0.27 K     3737.02 μs    ±27.80%     3603.24 μs     6261.40 μs
tuple grow_append                        0.00007 K 13584333.49 μs     ±0.00% 13584333.49 μs 13584333.49 μs
tuple grow_prepend                       0.00006 K 16420455.62 μs     ±0.00% 16420455.62 μs 16420455.62 μs
list grow_append concat                  0.00004 K 22971996.78 μs     ±0.00% 22971996.78 μs 22971996.78 μs
list grow_append                         0.00004 K 23192857.58 μs     ±0.00% 23192857.58 μs 23192857.58 μs
3 Likes