I've been wondering lately how various operations I perform on basic types like strings and integers work in terms of performance, and I figure I could get a much better idea of this if I knew how those basic types were implemented (i.e. I've heard strings and integers are immutable in Python. Does that mean any operation that modifies one character in a string is O(n) because a completely new string has to be created? How about adding numbers?)
I'm curious about this in both Python and Perl, and felt silly asking basically the same question twice, so I'm just wrapping it into one.
If you can include some example operation costs with your answer, that would make it even more helpful.
Perl strings definitely are not immutable.  Each string has a buffer, the initial offset of the string in the buffer, the length of buffer, and the amount of the buffer used.  Additionally, for utf8 strings, the character length is cached when it needs to be calculated.  At one point, there was some caching of additional character offset to byte offset information too, but I'm not certain that's still in place.
If the buffer needs to be increased, it reallocs it.  Perl on many platforms knows the granularity of the system malloc, so it can allocate a, say, 14 byte buffer for a 11 byte string, knowing that that won't actually take any additional memory.
The initial offset allows O(1) removal of data from the beginning of the string.
How are basic data types (strings and integers) implemented in Python and Perl