csv.DictWriter is slow when writing files with large number of columns

[mtraskin]

BPO	18219
Nosy	@terryjreedy, @vstinner, @bitdancer, @methane, @serhiy-storchaka, @Mariatta, @hughdbrown
PRs	[Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
Files	csvdictwriter.patch csvdictwriter.v2.patch csvdictwriter.v3.patch csvdictwriter.v4.patch issue18219.patch issue18219v2.patch issue18219v3.patch issue18219v4.patch issue18219v5.patch issue18219v6.patch issue18219v7.patch issue18219v8.patch issue18219v9.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2016-10-21.10:54:34.855>
created_at = <Date 2013-06-15.05:12:39.063>
labels = ['3.7', 'library', 'performance']
title = 'csv.DictWriter is slow when writing files with large number of columns'
updated_at = <Date 2017-03-31.16:36:23.298>
user = 'https://bugs.python.org/mtraskin'

bugs.python.org fields:

activity = <Date 2017-03-31.16:36:23.298>
actor = 'dstufft'
assignee = 'none'
closed = True
closed_date = <Date 2016-10-21.10:54:34.855>
closer = 'methane'
components = ['Library (Lib)']
creation = <Date 2013-06-15.05:12:39.063>
creator = 'mtraskin'
dependencies = []
files = ['30598', '30605', '31297', '31570', '45167', '45168', '45169', '45170', '45172', '45173', '45174', '45175', '45176']
hgrepos = []
issue_num = 18219
keywords = ['patch']
message_count = 23.0
messages = ['191197', '191198', '191263', '191604', '195233', '195245', '196821', '279058', '279101', '279105', '279107', '279108', '279109', '279115', '279116', '279117', '279118', '279119', '279120', '279121', '279124', '279128', '279129']
nosy_count = 10.0
nosy_names = ['terry.reedy', 'peter.otten', 'vstinner', 'r.david.murray', 'methane', 'python-dev', 'serhiy.storchaka', 'mtraskin', 'Mariatta', 'hughdbrown']
pr_nums = ['552']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue18219'
versions = ['Python 3.6', 'Python 3.7']

[mtraskin]

_dict_to_list method of the csv.DictWriter objects created with extrasaction="raise" uses look-up in the list of field names to check if current row has any unknown fields. This results in O(n^2) execution time and is very slow if there are a lot of columns in a CSV file (in hundreds or thousands). Replacing look-up in a list with a look-up in a set solves the issue (see the attached patch).

[serhiy-storchaka]

I think there is no need in public fieldset property. Just use private self._fieldset field in private _dict_to_list() method.

[mtraskin]

Any way is fine with me. If you prefer to avoid having public filedset property, please use the attached patch.

[terryjreedy]

What is the purpose in touching fieldnames, either in tuple-izing it or in making it private and wrapped with a property. If someone wants to modify it, that is up to them. In any case, this change is not germane to the issue and could break code, so I would not make it.

wrong_fields could be calculated with
any(k for k in rowdict if k not in self._fieldset)
to stop on the first extra, if any.

That said, in 3.x, replacing

wrong_fields = <long expression>
if wrong_fields:
with
if rowdict.keys() - self._fieldset:
should be even faster because the iteration, which will nearly always go to completion, is entirely in C (or whatever).

Does test/text_cvs have tests for DictWriter, both with and without rowdict errors? If so, or if added, I would be willing to commit a patch that simply added ._fieldset and used it as above for a set difference.

Also, if you have not done so yet, please go to
http://www.python.org/psf/contrib/ and
http://www.python.org/psf/contrib/contrib-form/ new electronic form
and submit a contributor agreement. An '*' will appear after your name here when it is processed.

[mtraskin]

What is the purpose in touching fieldnames [...]

Wrapping the fieldnames property and tupleizing it guarantees that fieldnames and _fieldset fields are consistent.
Otherwise, having a separate _fieldset field means that someone who is modifying the fieldnames field will not modify the _fieldset. This will result in inconsistent DictWriter behavior. Normal DictWriter users (ones that do not modify fieldnames after DictWriter was created) will not notice this wrapper. "Non-normal" DictWriter will have their code broken, but it is better than having inconsistent internal data structures since these errors are very hard to detect. If you insist on keeping the interface intact, then use the attached v3 of the patch: it creates a fieldset object every time the _dict_to_list method is executed. This does slow execution down, but performance is acceptable, just about 1.5 time slower than version with _fieldset field.

wrong_fields could be calculated with [...]
I believe it is better to report all wrong fields at ones. In addition this optimization is meaningless, since usually, unless something is wrong, the field check will require full scan of the rowdict.

That said, in 3.x, replacing [...]

In 2.x the list comprehension version is faster than the set difference version. In 3.x the set difference is slightly faster (maybe 10% faster). However, list comprehension works both in 2.x and 3.x, while set difference requires different code for them. Hence I prefer sticking with list comprehension.

Does test/text_cvs have tests [...]
No there are no tests for wrong fields. Correct fields are already checked with standard writing tests. I do not know how you write tests for exception handling. If you provide a link with instructions, I can write the missing test part.

Also, if you have not done so yet, please go to [...]
I have already done this.

[peterotten]

Note that set operations on dict views work with lists, too. So the only change necessary is to replace

wrong_fields = [k for k in rowdict if k not in self.fieldnames]

with

wrong_fields = rowdict.keys() - self.filenames

(A backport to 2.7 would need to replace keys() with viewkeys())

[mtraskin]

Peter, thank you for letting me know that views work with list, I was not aware of this. This is indeed the best solution and it also keeps the DictWriter interface unchanged.

Terry, attached patch contains the DictWriter change and a test case in test_csv.py.

[hughdbrown]

I came across this problem today when I was using a 1000+ column CSV from a client. It was taking about 15 minutes to process each file. I found the problem and made this change:

            # wrong_fields = [k for k in rowdict if k not in self.fieldnames]
            wrong_fields = set(rowdict.keys()) - set(self.fieldnames)

And my processing time went down to 12 seconds per file -- a 75x speedup.

It's kind of sad that this change has been waiting for over three years when it is so simple. Any chance we could make one of the acceptable code changes and release it?

[Mariatta]

Hello, please review my patch.

I used set subtraction to calculate wrong_fields, added more test cases, and clarify documentation with regards to extrasaction parameter.

Please let me know if this works.

Thanks :)

[hughdbrown]

Fabulous. Looks great. Let's ship!

It is not the *optimal* fix for 3.x platforms. A better fix would calculate the set of fieldnames only once in __init__ (or only as often as fieldnames is changed).

But I stress that it is a robust change that works in versions 2.7 through 3.x for sure. And it is *way* better than the alternative of searching a list.

[Mariatta]

Thanks Hugh,

Are you thinking of something like the following?

class DictWriter:
    def __init__(self, f, fieldnames, restval="", extrasaction="raise",
                 dialect="excel", *args, **kwds):
        self._fieldnames = fieldnames    # list of keys for the dict
        self._fieldnames_set = set(self._fieldnames)

    @property
    def fieldnames(self):
        return self._fieldnames

    @fieldnames.setter
    def fieldnames(self, value):
        self._fieldnames = value
        self._fieldnames_set = set(self._fieldnames)


    def _dict_to_list(self, rowdict):
        if self.extrasaction == "raise":
            wrong_fields = rowdict.keys() - self._fieldnames_set
     
    ...

If so, I can work on another patch.
Thanks.

[hughdbrown]

Mariatta:

Yes, that is what I was thinking of.

That takes my 12 execution time down to 10 seconds. (Or, at least, a fix I did of this nature had that effect -- I have not timed your patch but it should be the same.)