[RFC] FastDiffRunner

[benlau]

Hello,

I am going to write a FastDiffRunner to offer a diff runner with better performance. And here is the proposed API. If anyone is interested, please feel free to comment and making suggestion.

Objective

The current implementation of DiffRunner requires the user to convert a C++ data structure into QVariantMap then perform a comparison. It is an easy to use solution and fast enough for the small amount of data. But since the average time complexity is O(n) even the data is unchanged. Therefore, it may be difficult to handle a huge amount of data.

To solve this problem, a new FastDiffRunner is proposed. It uses the implicitly shared data class (Immutable type) in Qt. The big-O to compare data without changes is O(1). And it doesn't convert data to QVariantMap for comparison. It should be much faster than the original DiffRunner.

Preparation

1) Immutable Data

FastDiffRunner only works with an immutable data type. User should create their data structure by File -> New File or Project -> C++ Class. Tick Include QShared Data in Qt Creator

Example (Generated by Qt Creator)

class CustomDataData;

class CustomData
{
public:
    CustomData();
    CustomData(const CustomData &);
    CustomData &operator=(const CustomData &);
    ~CustomData();

private:
    QSharedDataPointer<CustomDataData> data;
};

2) Implements isSharedWith() and key() function

class CustomDataData;

class CustomData
{
    Q_GADGET

public:
    CustomData();
    CustomData(const CustomData &);
    CustomData &operator=(const CustomData &);
    ~CustomData();

    bool isSharedWith(const CustomData& other);

    Q_INVOKABLE QVariant key(); // Optional function. 

private:
    QSharedDataPointer<CustomDataData> data;
};

inline bool CustomData::isSharedWith(const CustomData &other)
{
    return this->data == other.data;
}

3) Implements custom convertor function [Optional]

QVariantMap convert(const CustomData& data) {
  /// Insert your code here
}

If you have declared your property via Q_PROPERTY(), then it is not needed.

Usage

The interface of FastDiffRunner is almost same as the DiffRunner, expect you may need apply a custom data convertor function and doesn't need to set key field.

QList<CustomData> previous, current; 

// load previous and current 

QSFastDiffRunner<CustomData> runner(convert); 

QList<QSPatch> patches = runner.compare(previous, current);

runner.patch(listModel, patches);

Pros & Cons

Pros

1. O(1) comparison for unchanged data

Cons

1. It don't work for JavaScript

Request for Comment

If you have any suggestion toward the design, please feel free to leave a comment here. Thx

Discussion

Discussion 1

Interface Class

Should it use an abstract interface instead of just using Q_GADGET?

Example

class QSImmutable {
  Q_GADGET
public:
  bool iSharedWith(const QSImmutable*) = 0;
  QVariant key() const;
  bool hasKey() const; // User should implement this function if key is present in the data structure
}

[polarathene]

Could similar variants be used for JS or other bindings like Python?(Or does that utilize C++ and thus the fast diff uder the hood?)

[benlau]

hi @polarathene ,

yes. I will bring the fast diff to JavaScript too (still under development). But user need to update their data by following the Immutable Update Patterns · Redux

That is the proposal:

ImmutableListModel {
    id: model
}

var list = [a,b,c]; // where a , b, c is an object type
model.source = list;

// append a new item
list = list.slice(0); // make a shadow copy
list.push(d);
model.source = list;

// update an field in the first item
list = list.slice(0);
list[0] = assign({} , list[0], changes); // e.g Lodash.assign 
model.source = list;

If you have any question / suggestion, please feel free to raise.

[polarathene]

Will there be support or information on how to implement for other language bindings to Qt/QML like Python?

Thanks for the immutable patterns link, I think I've done shallow copies in the past with spread like the example, would it be good to use something like ImmutableJS?

Presently I'm just using an Item with properties(that might have nested property items) and referring to it via my elements, when I update that data_item element properties it seems to update the bindings to everything else. I'm still learning QML/Python, only sent a custom list model with roles to QML ListView so far(seems to work fine if I bind the model to the data_item properties and have ListView reference that property for the model). Haven't tried modifying data via Python yet, The way I understand QSyncable if it had support with my backend language is I'd modify my model data on the bakend and it'd update/sync a copy between QML and backend language. If you do look into Python there seems to be Redux ports(so I'd sync that state object/store to QML with QSyncable and presumably use it like I am currently with the data_item I mentioned earlier?

---

You seem to do quite a few Qt/QML projects, maybe you would take interest in reviving the Quickly project which aimed to allow modern JS transpiled to QML, hasn't been maintained in a while. Would allow for fetch/promises/async?/short-lamda/destructure/spread/etc

There seems to be some effort to make a React-Native binding for Qt(ReaQt), but there isn't much out there beyond the talk so maybe it won't see the light of day from HP/Qt :( There was also react-qml that hasn't seen any love since 2015.

[benlau]

Will there be support or information on how to implement for other language bindings to Qt/QML like Python?

I don't familiar with C++ with Python. So now I don't have plan or pointer for this.

btw, any suggested immutable data type library I could take a look for reference?

Thanks for the immutable patterns link, I think I've done shallow copies in the past with spread like the example, would it be good to use something like ImmutableJS?

It seems that ImmutableJS is more complicated to use when compare to the immutable update pattern. Just my 2 cents.

---

You seem to do quite a few Qt/QML projects, maybe you would take interest in reviving the Quickly project which aimed to allow modern JS transpiled to QML, hasn't been maintained in a while. Would allow for fetch/promises/async?/short-lamda/destructure/spread/etc

In fact, I have started another project: e-fever/qmljsify: Convert an NPM package into a QML friendly JavaScript file

But the objective is different. Quickly compiles a ES6 JS + QML , but qmljsify only compile library from npm to a QML friendly way. It don't touch the QML files.

There seems to be some effort to make a React-Native binding for Qt(ReaQt), but there isn't much out there beyond the talk so maybe it won't see the light of day from HP/Qt :( There was also react-qml that hasn't seen any love since 2015.

Although I have made few projects to bring Redux / Flux to QML, I don't quite understand why people would like to bring React to QML? The concept of QML and React itself is not quite compatible. It will just like using React within Angular...

[polarathene]

I don't quite understand why people would like to bring React to QML? The concept of QML and React itself is not quite compatible. It will just like using React within Angular...

Similar reasons to the ReaQt video I imagine? Perhaps it would be more suited to Qt Widgets or the Qt 6 API/backend unification that seems to be planned for 2019.

I don't see how it's like using React within Angular? You can declare components like QML components, just in JSX instead of QML(which they'd get transpiled to like Quickly might have been able to do?). The benefit is similar/same code that can be used elsewhere beyond QML as a platform, the richer syntax of modern JS and wide range of library support(especially with Redux and it's middleware, including integration with React with dumb/smart components), I also like how styled-components approached styling, not sure if that'd map well to QML styling however.

You have much more experience with QML than I do, so perhaps I'm mistaken.

I don't familiar with C++ with Python. So now I don't have plan or pointer for this. btw, any suggested immutable data type library I could take a look for reference?

I am using PySide2/PyQt5 python packages that provide the Qt/QML integration. I am new to python, I've not looked into any immutable data type library for it. It seems to be a popular choice for doing Qt interfaces with if not C++/JS.

In fact, I have started another project: e-fever/qmljsify: Convert an NPM package into a QML friendly JavaScript file But the objective is different. Quickly compiles a ES6 JS + QML , but qmljsify only compile library from npm to a QML friendly way. It don't touch the QML files.

That looks nice, but sounds similar to QMLify that Quickly uses? I think it can do similar? I guess your one is meant to compile QML module or just JS file that is transpiled to QML JS? Quickly sounds quite appealing that you can write your QML with modern JS and import modern JS as modules and then transpile to something QML will be happy with. Common thing to do from web dev world. I can see advantage of distributing already transpiled JS for others to use too I guess. Does Quickly address the problems you mention in your repo having trouble with?