Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Line number storage scheme is inefficient #648

Closed
pfalcon opened this issue Jun 2, 2014 · 5 comments

Comments

Projects
None yet
3 participants
@pfalcon
Copy link
Contributor

commented Jun 2, 2014

In the following dump:

assign byte code: code=0x2eb160 len=354 n_pos_args=3 n_kwonly_args=0 flags=40
  arg names: n iterable key
 60 00 00 00 5f 01 00 00 66 01 00 00 e5 e0 e0 e0
 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0
 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0
 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0 e0
 e0 e0 e0 e0 e0 e0 e0 e0 e0 c0 28 27 2f 25 23 27
 30 75 23 2c 2e 45 28 75 27 31 2a 6e 2c 39 2a 00
 12 00 01 00 00 20 14 01 62 1a 47 4a 80 27 6e 21
 94 01 33 03 27 70 27 82 69 23 03 14 01 94 02 94
File heapq.py, block 'nlargest' (354 bytes)
(N_STATE 18)
(N_EXC_STACK 1)
(NUM_LOCAL 0)
  bc=-5 line=1
  bc=0 line=8
  bc=0 line=15
  bc=0 line=22
  bc=0 line=29

All those e0 are for nothing but inefficiently encoding initial line number of code block. As each e0 can increment line number only by 7, there is for many, many of them. Proposal: let's have initial line number encoded in a special, explicit way - for example, as VM varlen encoding, or we want more variety, as 2 bytes, but 0xffff meaning that there're another 2 bytes (recursive) to account for long source files.

@dpgeorge

This comment has been minimized.

Copy link
Member

commented Jun 2, 2014

Well, for micro applications, you probably don't have 10's of lines documentation at the start of the file, so it's not so bad :)

This scheme was designed to be dead simple to implement, but I agree it could be improved.

@pfalcon pfalcon added the prio-med label Jul 20, 2014

@dpgeorge

This comment has been minimized.

Copy link
Member

commented Jul 31, 2014

Here is a histogram showing the frequency of having to skip n bytes and n lines. The data is collected from the CPython 3.4 stdlib, being 111,000 lines of Python code, and gives 125,000 data points (accumulated to a histogram). Note the log-log scale.

bytes-lines

Read it as follows: more than 50% of the time, you just need to skip 1 line (the blue curve is highest at 1). The most common number of bytes to skip is 5 (the red curve is highest at 5). 0.1% of the time you need to skip more than 30 lines.

dpgeorge added a commit that referenced this issue Jul 31, 2014

py: Improve encoding scheme for line-number to bytecode map.
Reduces by about a factor of 10 on average the amount of RAM needed to
store the line-number to bytecode map in the bytecode prelude.

Using CPython3.4's stdlib for statistics: previously, an average of
13 bytes were used per (bytecode offset, line-number offset) pair, and
now with this improvement, that's down to 1.3 bytes on average.

Large RAM usage before was due to some very large steps in line numbers,
both from the start of the first line in a function way down in the
file, and also functions that have big comments and/or big strings in
them (both cases were significant).

Although the savings are large on average for the CPython stdlib, it
won't have such a big effect for small scripts used in embedded
programming.

Addresses issue #648.
@dpgeorge

This comment has been minimized.

Copy link
Member

commented Jul 31, 2014

Now much more efficient.

Based on the above statistics (using CPython3.4 stdlib), I got it close to optimal for this suite of scripts. Original method used 13 bytes per (bytecode, line number) pair; new method uses just 1.3 on average. The method is tuned for this set of scripts, but they should be indicative of general Python scripts.

In the new method, there are 2 encoding schemes: a 1 byte one, and a 2 byte one. The 1 byte one is used for 75% of the (bytecode, line number) pairs.

Note that there are a decent amount of cases (around 10%) where large line skips occur within the function (not just the first line of the function being a large number). Thus, it's important to have the coding scheme work within functions, not just to optimise the first line being large. Also, it's simpler code not having a special case for the first function.

@dpgeorge dpgeorge closed this Jul 31, 2014

@Neon22

This comment has been minimized.

Copy link
Contributor

commented Aug 1, 2014

FWIW that's very impressive. congratulations

@dpgeorge

This comment has been minimized.

Copy link
Member

commented Aug 1, 2014

Thanks :) It was a nice combination of analysis, statistics, engineering and coding!

tannewt added a commit to tannewt/circuitpython that referenced this issue Jun 2, 2018

Use the external crystal on SAMD21 again.
Also, re-enable calibration storage for CircuitPlayground Express.
Tested with a 500hz PWMOut on Metro M0 with Saleae:
 * with crystal 500hz
 * with usb 500hz +- 0.1hz
 * without either 487hz += 0.1hz

SAMD51 is skipped due to DFLL errata and the fact it defaults to a
factory calibrated 48mhz that works fine for USB.

Fixes micropython#648
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.