为什么Document.insertString()的运行时不是常量时间？

Question

我正在创建一个记录器,以显示输出作为更大的Java swing GUI的一部分.不幸的是,我添加它后经历了一个减速.我已经跟踪过这个问题了Document.insertString().

我做了一个测试,显示了这种放缓:

LogPanel.java

public class LogPanel extends JPanel{
    private static final SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    private JEditorPane textPane;
    private static int numTextRows = 50;
    private SimpleAttributeSet keyWord;
    private Document document;

   public LogPanel() {
        super(new BorderLayout());
        add(makePanel(), BorderLayout.CENTER);
    }

    private Component makePanel() {
        // Just a text area that grows and can be scrolled.
        textPane = new JTextPane();
        document = textPane.getDocument();
        keyWord = new SimpleAttributeSet();
        StyleConstants.setForeground(keyWord, Color.BLACK);

        //textArea.setRows(numTextRows);
        textPane.setEditable(false);
        textPane.setFont(new Font("monospaced", Font.PLAIN, 12));

        DefaultCaret caret = (DefaultCaret) textPane.getCaret();
        caret.setUpdatePolicy(DefaultCaret.ALWAYS_UPDATE);

        //Wrap the textPane in a JPanel with BorderLayout so that the text does not wrap
        JPanel textPaneWrapper = new JPanel();
        textPaneWrapper.setLayout(new BorderLayout());
        textPaneWrapper.add(textPane);

        JScrollPane areaScrollPane = new JScrollPane(textPaneWrapper);
        areaScrollPane.getVerticalScrollBar().setUnitIncrement(20);
        //JScrollPane areaScrollPane = new JScrollPane(textPane);
        areaScrollPane.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);
        areaScrollPane.setHorizontalScrollBarPolicy(JScrollPane.HORIZONTAL_SCROLLBAR_AS_NEEDED);
        areaScrollPane.setPreferredSize(new Dimension(250, 250));
//        builder.add(areaScrollPane, cc.xywh(1, 3, 3, 1));

        StyleConstants.setBackground(keyWord, areaScrollPane.getBackground());
        textPane.setBackground(areaScrollPane.getBackground());

        return areaScrollPane;
    }

    public void appendResult(final String action, final String result, final Color color) {
        Date now = new Date();
        String strDate = df.format(now);
        String paddedAction = String.format("%-19s", action);
        StyleConstants.setForeground(keyWord, color);

        try {
            document.insertString(document.getLength(), strDate + "   " + paddedAction + "   " + result + "\n", keyWord);
        } catch (BadLocationException e) {
            throw new RuntimeException(e);
        } 

        if(!textPane.hasFocus()) {
            textPane.setCaretPosition(document.getLength());
        }
    }

    public void appendResult(String action, String result) {
        appendResult(action, result, Color.BLACK);
    }
}

LogTester.Java

public class LogTester extends JFrame{
    private LogPanel logPanel;
    private JButton pushMe;

    public LogTester(){
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setLayout(new GridBagLayout());

        logPanel = new LogPanel();
        this.add(logPanel);

        pushMe= new JButton("Press Me");
        LogTester self=this;
        pushMe.addActionListener(new ActionListener(){
            public void actionPerformed(ActionEvent e) {
                self.addLotsOfStuff();
            }
        });
        this.add(pushMe);

        this.pack();
        this.setVisible(true);

    }

    public void addLotsOfStuff(){
        for(int i=0; i<1000; i+=1){
            long start=System.currentTimeMillis();
            for(int j=0; j<1000; j+=1){
                String str="This is a very long peice of text designed to test the capabilites of our log panel. Move along, nothing to see here.";
                logPanel.appendResult("HERP",str);
            }
            long end=System.currentTimeMillis();
            System.out.println(end-start);
        }
    }

    public static void main(String args[]){
        LogTester test=new LogTester();
    }
}

上面的程序试图将大量的行写入a JTextPane,利用它Document.insertString().该计划的结果涉及:

由于某种原因,每次调用此函数都会增加下一次调用的运行时间:它看起来是线性的,甚至是温和的指数.这可能意味着文档的所有先前内容都被复制到每个插入,而不是附加的新字符串(以某种链表方式)

与Java GUI冻结不同,因为insertString方法？我主要关心的是函数运行时间的增加,而不是应用程序的空闲时间.如果每个单独的调用变得非常慢,则添加线程将无济于事.

与Limit JTextPane空间使用不同,我不关心大内存使用情况.如果文档很大,它将使用大量内存.我只是不明白为什么会影响向Document插入更多信息的运行时间.

也许减速可归因于这个插入位置内存泄漏？

为了获得恒定的时间,我必须覆盖JTextPane或Document的哪些部分insertString()？

Answer 1

数组的增长几乎是线性的，但实际上不是线性的。

一旦超过 1 级缓存行的大小，您将使用另一个缓存行，直到：

• 没有空闲的缓存行，因此您必须逐出现有的行缓存，从 2 级缓存行的一部分填充它。
• 没有空闲的 2 级缓存行，因此您必须逐出其中之一，从（通常）通用 RAM 请求中填充它。
• 您的一般 RAM 请求太大，无法放入一个请求中，并且由于其计数或内存芯片位置，无法共同获取所请求的一组页面。

这意味着，即使对于线性运算，真正小的东西的运行速度也比处理大量数据的相同线性算法快得多。

因此，在决定算法是否为 O(n) 或其他算法时，重要的是要记住，这样的决定是基于对计算模型的期望的基本理解。Big-O 表示法假设所有 RAM 读取在时间上都是相等的，并且计算（操作）在时间上也是相等的。在这样的限制下，将操作次数与数据量进行比较仍然有意义；但是，假设挂钟时间准确则不然。